[Scip] non valid solution using SCIP in the pricing
Hélène Toussaint
helene.toussaint at isima.fr
Thu Feb 14 08:58:50 MET 2013
Dear all,
I use SCIP 3.0.0 to run a column generation program. I have sometimes
(very rarely) an issue when solving my sub problem with SCIP during the
pricing: the solution doesn't respect all the constraints. I enclose a
LP ("subPb.lp") for which SCIP gives the solution y11=1; y18=1; y25=1
(all other variables are 0). The constraint cR_0 is violated by this
solution (since it involves " cR_0 : 18 <= 15"). This problem only
occurs when I use a subSCIP: if I use SCIPreadProb directly on the LP
enclosed then SCIP gives the exact result (there exists several
solutions whose objective = 1) .
I had a look to the transformed problem (enclosed as "transSubPb.lp").
In this transformed problem, the bounds force variables t_y7, t_y17 and
t_26 to be 1. But this violate the cR_2 constraint, so this problem is
infeasible (while the original problem is feasible...).
I have encountered a very similar problem few months ago (solutions
violating constraints on instances for which the objective function is
parallel to a ranged row) and it was solved by the enclosed patch (given
by Stefan). But this time the violated constraint appears in the
transformed problem.
Could you please help me with this issue?
Best regards,
Hélène
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20130214/47ed3f48/attachment.html
-------------- next part --------------
--- a/src/scip/cons_linear.c
+++ b/src/scip/cons_linear.c
@@ -6533,11 +6530,22 @@ SCIP_RETCODE updateCutoffbound(
}
else
{
- /* in case the cutoff bound is worse then currently known one we avoid additionaly enforcement and
- * propagation
+ SCIP_CONSDATA* consdata;
+
+ consdata = SCIPconsGetData(cons);
+ assert(consdata != NULL);
+
+ /* we cannot disable the enforcement and propagation on ranged rows, because the cutoffbound could only have
+ * resulted from one side
*/
- SCIP_CALL( SCIPsetConsEnforced(scip, cons, FALSE) );
- SCIP_CALL( SCIPsetConsPropagated(scip, cons, FALSE) );
+ if( SCIPisInfinity(scip, -consdata->lhs) || SCIPisInfinity(scip, consdata->rhs) )
+ {
+ /* in case the cutoff bound is worse then the currently known one, we additionally avoid enforcement and
+ * propagation
+ */
+ SCIP_CALL( SCIPsetConsEnforced(scip, cons, FALSE) );
+ SCIP_CALL( SCIPsetConsPropagated(scip, cons, FALSE) );
+ }
}
return SCIP_OKAY;
-------------- next part --------------
\ SCIP STATISTICS
\ Problem name : sousPb
\ Variables : 40 (40 binary, 0 integer, 0 implicit integer, 0 continuous)
\ Constraints : 210
\ Obj. scale : 1
\ Obj. offset : 0
Maximize
Obj: +0.6 y1 +0.4 y2 +0.4 y3 +0.6 y4 +0.6 y5 +0.4 y6 +0.4 y7 +0.4 y8 +0.2 y9 +0.4 y10 +0.2 y11 +0.2 y12
+0.4 y13 +0.4 y15 +0.4 y16 +0.4 y17 +0.6 y18 +0.8 y19 +0.6 y20 +0.2 y22 +0.6 y23 +0.2 y24 +0.4 y25
+0.6 y26 +1 y27 +0.4 y28 +1 y29 +1 y30 -0.2 t1_20 -0.2 t2_19 -0.4 t8_30 -0.2 t9_23 -0.2 t13_16 -0.2 t16_17
-0.2 t16_22 -0.2 t17_19 -0.2 t22_30 -0.4 t25_27
Subject to
sum_1_20: +1 y1 +1 y20 -1 t1_20 <= +1
sum_2_19: +1 y2 +1 y19 -1 t2_19 <= +1
sum_8_30: +1 y8 +1 y30 -1 t8_30 <= +1
sum_9_23: +1 y9 +1 y23 -1 t9_23 <= +1
sum_13_16: +1 y13 +1 y16 -1 t13_16 <= +1
sum_16_17: +1 y16 +1 y17 -1 t16_17 <= +1
sum_16_22: +1 y16 +1 y22 -1 t16_22 <= +1
sum_17_19: +1 y17 +1 y19 -1 t17_19 <= +1
sum_22_30: +1 y22 +1 y30 -1 t22_30 <= +1
sum_25_27: +1 y25 +1 y27 -1 t25_27 <= +1
cR_0: +1 y1 +4 y2 +5 y3 +6 y4 +4 y5 +10 y6 +3 y7 +2 y8 +4 y9 +3 y10 +3 y11 +2 y12 +4 y13 +2 y14 +9 y15
+6 y16 +2 y17 +7 y18 +10 y19 +6 y20 +3 y21 +1 y22 +7 y23 +4 y24 +8 y25 +10 y26 +1 y27 +6 y28 +6 y29
+9 y30 <= +15
cR_1: +6 y1 +7 y2 +4 y3 +10 y4 +9 y5 +2 y6 +6 y7 +9 y8 +3 y9 +10 y10 +2 y11 +6 y12 +1 y13 +3 y14 +1 y15
+4 y16 +3 y17 +6 y18 +5 y19 +8 y20 +6 y21 +1 y22 +5 y23 +9 y24 +5 y25 +4 y26 +10 y27 +6 y28 +6 y29 +5 y30
<= +15
cR_2: +8 y1 +7 y2 +1 y3 +3 y4 +8 y5 +2 y6 +1 y7 +1 y8 +2 y9 +3 y10 +1 y11 +1 y12 +6 y13 +3 y14 +7 y15
+3 y16 +10 y17 +10 y18 +4 y19 +8 y20 +10 y21 +4 y22 +1 y23 +8 y24 +1 y25 +7 y26 +6 y27 +6 y28 +10 y29
+4 y30 <= +17
cR_3: +6 y1 +4 y2 +7 y3 +9 y4 +3 y5 +5 y6 +5 y7 +2 y8 +3 y9 +8 y10 +4 y11 +1 y12 +10 y13 +9 y14 +10 y15
+1 y16 +9 y17 +5 y18 +4 y19 +9 y20 +2 y21 +6 y22 +3 y23 +4 y24 +7 y25 +2 y26 +9 y27 +10 y28 +10 y29
+9 y30 <= +16
cC_1_4: +1 y1 +1 y4 <= +1
cC_1_6: +1 y1 +1 y6 <= +1
cC_1_7: +1 y1 +1 y7 <= +1
cC_1_8: +1 y1 +1 y8 <= +1
cC_1_9: +1 y1 +1 y9 <= +1
cC_1_10: +1 y1 +1 y10 <= +1
cC_1_13: +1 y1 +1 y13 <= +1
cC_1_15: +1 y1 +1 y15 <= +1
cC_1_17: +1 y1 +1 y17 <= +1
cC_1_18: +1 y1 +1 y18 <= +1
cC_1_19: +1 y1 +1 y19 <= +1
cC_1_21: +1 y1 +1 y21 <= +1
cC_1_22: +1 y1 +1 y22 <= +1
cC_1_23: +1 y1 +1 y23 <= +1
cC_1_24: +1 y1 +1 y24 <= +1
cC_1_25: +1 y1 +1 y25 <= +1
cC_1_26: +1 y1 +1 y26 <= +1
cC_1_27: +1 y1 +1 y27 <= +1
cC_1_28: +1 y1 +1 y28 <= +1
cC_1_29: +1 y1 +1 y29 <= +1
cC_1_30: +1 y1 +1 y30 <= +1
cC_2_16: +1 y2 +1 y16 <= +1
cC_2_20: +1 y2 +1 y20 <= +1
cC_2_21: +1 y2 +1 y21 <= +1
cC_2_23: +1 y2 +1 y23 <= +1
cC_2_24: +1 y2 +1 y24 <= +1
cC_2_27: +1 y2 +1 y27 <= +1
cC_2_28: +1 y2 +1 y28 <= +1
cC_2_29: +1 y2 +1 y29 <= +1
cC_2_30: +1 y2 +1 y30 <= +1
cC_3_5: +1 y3 +1 y5 <= +1
cC_3_6: +1 y3 +1 y6 <= +1
cC_3_8: +1 y3 +1 y8 <= +1
cC_3_10: +1 y3 +1 y10 <= +1
cC_3_11: +1 y3 +1 y11 <= +1
cC_3_12: +1 y3 +1 y12 <= +1
cC_3_13: +1 y3 +1 y13 <= +1
cC_3_14: +1 y3 +1 y14 <= +1
cC_3_16: +1 y3 +1 y16 <= +1
cC_3_18: +1 y3 +1 y18 <= +1
cC_3_19: +1 y3 +1 y19 <= +1
cC_3_20: +1 y3 +1 y20 <= +1
cC_3_21: +1 y3 +1 y21 <= +1
cC_3_22: +1 y3 +1 y22 <= +1
cC_3_23: +1 y3 +1 y23 <= +1
cC_3_24: +1 y3 +1 y24 <= +1
cC_3_26: +1 y3 +1 y26 <= +1
cC_3_27: +1 y3 +1 y27 <= +1
cC_3_29: +1 y3 +1 y29 <= +1
cC_3_30: +1 y3 +1 y30 <= +1
cC_4_6: +1 y4 +1 y6 <= +1
cC_4_8: +1 y4 +1 y8 <= +1
cC_4_10: +1 y4 +1 y10 <= +1
cC_4_17: +1 y4 +1 y17 <= +1
cC_4_18: +1 y4 +1 y18 <= +1
cC_4_19: +1 y4 +1 y19 <= +1
cC_4_21: +1 y4 +1 y21 <= +1
cC_4_22: +1 y4 +1 y22 <= +1
cC_4_23: +1 y4 +1 y23 <= +1
cC_4_27: +1 y4 +1 y27 <= +1
cC_4_29: +1 y4 +1 y29 <= +1
cC_5_10: +1 y5 +1 y10 <= +1
cC_5_11: +1 y5 +1 y11 <= +1
cC_5_12: +1 y5 +1 y12 <= +1
cC_5_13: +1 y5 +1 y13 <= +1
cC_5_14: +1 y5 +1 y14 <= +1
cC_5_19: +1 y5 +1 y19 <= +1
cC_5_20: +1 y5 +1 y20 <= +1
cC_5_21: +1 y5 +1 y21 <= +1
cC_5_22: +1 y5 +1 y22 <= +1
cC_5_23: +1 y5 +1 y23 <= +1
cC_5_24: +1 y5 +1 y24 <= +1
cC_5_26: +1 y5 +1 y26 <= +1
cC_5_27: +1 y5 +1 y27 <= +1
cC_5_29: +1 y5 +1 y29 <= +1
cC_5_30: +1 y5 +1 y30 <= +1
cC_6_8: +1 y6 +1 y8 <= +1
cC_6_10: +1 y6 +1 y10 <= +1
cC_6_18: +1 y6 +1 y18 <= +1
cC_6_19: +1 y6 +1 y19 <= +1
cC_6_22: +1 y6 +1 y22 <= +1
cC_6_23: +1 y6 +1 y23 <= +1
cC_6_27: +1 y6 +1 y27 <= +1
cC_6_29: +1 y6 +1 y29 <= +1
cC_7_13: +1 y7 +1 y13 <= +1
cC_7_19: +1 y7 +1 y19 <= +1
cC_7_22: +1 y7 +1 y22 <= +1
cC_7_24: +1 y7 +1 y24 <= +1
cC_7_27: +1 y7 +1 y27 <= +1
cC_7_28: +1 y7 +1 y28 <= +1
cC_7_29: +1 y7 +1 y29 <= +1
cC_7_30: +1 y7 +1 y30 <= +1
cC_8_10: +1 y8 +1 y10 <= +1
cC_8_18: +1 y8 +1 y18 <= +1
cC_8_19: +1 y8 +1 y19 <= +1
cC_8_22: +1 y8 +1 y22 <= +1
cC_8_23: +1 y8 +1 y23 <= +1
cC_8_27: +1 y8 +1 y27 <= +1
cC_8_29: +1 y8 +1 y29 <= +1
cC_9_15: +1 y9 +1 y15 <= +1
cC_9_19: +1 y9 +1 y19 <= +1
cC_9_22: +1 y9 +1 y22 <= +1
cC_9_25: +1 y9 +1 y25 <= +1
cC_9_26: +1 y9 +1 y26 <= +1
cC_9_27: +1 y9 +1 y27 <= +1
cC_9_28: +1 y9 +1 y28 <= +1
cC_9_29: +1 y9 +1 y29 <= +1
cC_9_30: +1 y9 +1 y30 <= +1
cC_10_19: +1 y10 +1 y19 <= +1
cC_10_22: +1 y10 +1 y22 <= +1
cC_10_27: +1 y10 +1 y27 <= +1
cC_10_29: +1 y10 +1 y29 <= +1
cC_11_20: +1 y11 +1 y20 <= +1
cC_11_21: +1 y11 +1 y21 <= +1
cC_11_22: +1 y11 +1 y22 <= +1
cC_11_23: +1 y11 +1 y23 <= +1
cC_11_24: +1 y11 +1 y24 <= +1
cC_11_26: +1 y11 +1 y26 <= +1
cC_11_27: +1 y11 +1 y27 <= +1
cC_11_29: +1 y11 +1 y29 <= +1
cC_11_30: +1 y11 +1 y30 <= +1
cC_12_13: +1 y12 +1 y13 <= +1
cC_12_14: +1 y12 +1 y14 <= +1
cC_12_19: +1 y12 +1 y19 <= +1
cC_12_22: +1 y12 +1 y22 <= +1
cC_12_23: +1 y12 +1 y23 <= +1
cC_12_24: +1 y12 +1 y24 <= +1
cC_12_27: +1 y12 +1 y27 <= +1
cC_12_29: +1 y12 +1 y29 <= +1
cC_12_30: +1 y12 +1 y30 <= +1
cC_13_19: +1 y13 +1 y19 <= +1
cC_13_22: +1 y13 +1 y22 <= +1
cC_13_27: +1 y13 +1 y27 <= +1
cC_13_29: +1 y13 +1 y29 <= +1
cC_13_30: +1 y13 +1 y30 <= +1
cC_14_24: +1 y14 +1 y24 <= +1
cC_14_29: +1 y14 +1 y29 <= +1
cC_14_30: +1 y14 +1 y30 <= +1
cC_15_22: +1 y15 +1 y22 <= +1
cC_15_26: +1 y15 +1 y26 <= +1
cC_15_27: +1 y15 +1 y27 <= +1
cC_15_29: +1 y15 +1 y29 <= +1
cC_15_30: +1 y15 +1 y30 <= +1
cC_16_20: +1 y16 +1 y20 <= +1
cC_16_21: +1 y16 +1 y21 <= +1
cC_16_23: +1 y16 +1 y23 <= +1
cC_16_24: +1 y16 +1 y24 <= +1
cC_16_27: +1 y16 +1 y27 <= +1
cC_16_29: +1 y16 +1 y29 <= +1
cC_16_30: +1 y16 +1 y30 <= +1
cC_17_18: +1 y17 +1 y18 <= +1
cC_17_23: +1 y17 +1 y23 <= +1
cC_17_27: +1 y17 +1 y27 <= +1
cC_17_29: +1 y17 +1 y29 <= +1
cC_18_23: +1 y18 +1 y23 <= +1
cC_18_27: +1 y18 +1 y27 <= +1
cC_18_29: +1 y18 +1 y29 <= +1
cC_19_22: +1 y19 +1 y22 <= +1
cC_19_27: +1 y19 +1 y27 <= +1
cC_19_29: +1 y19 +1 y29 <= +1
cC_20_21: +1 y20 +1 y21 <= +1
cC_20_23: +1 y20 +1 y23 <= +1
cC_20_24: +1 y20 +1 y24 <= +1
cC_20_27: +1 y20 +1 y27 <= +1
cC_20_29: +1 y20 +1 y29 <= +1
cC_20_30: +1 y20 +1 y30 <= +1
cC_21_27: +1 y21 +1 y27 <= +1
cC_21_29: +1 y21 +1 y29 <= +1
cC_22_27: +1 y22 +1 y27 <= +1
cC_22_29: +1 y22 +1 y29 <= +1
cC_23_27: +1 y23 +1 y27 <= +1
cC_23_29: +1 y23 +1 y29 <= +1
cC_24_30: +1 y24 +1 y30 <= +1
cC_25_26: +1 y25 +1 y26 <= +1
cC_25_28: +1 y25 +1 y28 <= +1
cC_25_29: +1 y25 +1 y29 <= +1
cC_25_30: +1 y25 +1 y30 <= +1
cC_26_29: +1 y26 +1 y29 <= +1
cC_26_30: +1 y26 +1 y30 <= +1
cC_27_29: +1 y27 +1 y29 <= +1
sum2: +1 y1 +1 y2 +1 y3 +1 y4 +1 y5 +1 y6 +1 y7 +1 y8 +1 y9 +1 y10 +1 y11 +1 y12 +1 y13 +1 y14 +1 y15
+1 y16 +1 y17 +1 y18 +1 y19 +1 y20 +1 y21 +1 y22 +1 y23 +1 y24 +1 y25 +1 y26 +1 y27 +1 y28 +1 y29 +1 y30
>= +2
c_zero: +1 y4 +1 y16 <= +1
c_zero: +1 y7 +1 y18 <= +1
c_zero: +1 y5 +1 y15 <= +1
c_zero: +1 y4 +1 y25 <= +1
c_zero: +1 y16 +1 y22 <= +1
c_zero: +1 y1 +1 y11 <= +1
c_zero: +1 y1 +1 y5 <= +1
c_zero: +1 y18 +1 y28 <= +1
c_zero: +1 y10 +1 y25 <= +1
c_zero: +1 y26 +1 y27 <= +1
c_zero: +1 y16 +1 y17 <= +1
c_zero: +1 y6 +1 y17 <= +1
c_zero: +1 y13 +1 y21 <= +1
c_zero: +1 y11 +1 y17 <= +1
c_zero: +1 y2 +1 y11 <= +1
Bounds
0 <= y1 <= 1
0 <= y2 <= 1
0 <= y3 <= 1
0 <= y4 <= 1
0 <= y5 <= 1
0 <= y6 <= 1
0 <= y7 <= 1
0 <= y8 <= 1
0 <= y9 <= 1
0 <= y10 <= 1
0 <= y11 <= 1
0 <= y12 <= 1
0 <= y13 <= 1
0 <= y14 <= 1
0 <= y15 <= 1
0 <= y16 <= 1
0 <= y17 <= 1
0 <= y18 <= 1
0 <= y19 <= 1
0 <= y20 <= 1
0 <= y21 <= 1
0 <= y22 <= 1
0 <= y23 <= 1
0 <= y24 <= 1
0 <= y25 <= 1
0 <= y26 <= 1
0 <= y27 <= 1
0 <= y28 <= 1
0 <= y29 <= 1
0 <= y30 <= 1
0 <= t1_20 <= 1
0 <= t2_19 <= 1
0 <= t8_30 <= 1
0 <= t9_23 <= 1
0 <= t13_16 <= 1
0 <= t16_17 <= 1
0 <= t16_22 <= 1
0 <= t17_19 <= 1
0 <= t22_30 <= 1
0 <= t25_27 <= 1
Binaries
y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y11 y12 y13 y14 y15 y16 y17 y18 y19 y20 y21 y22 y23 y24 y25 y26 y27 y28
y29 y30 t1_20 t2_19 t8_30 t9_23 t13_16 t16_17 t16_22 t17_19 t22_30 t25_27
End
-------------- next part --------------
\ SCIP STATISTICS
\ Problem name : t_sousPb
\ Variables : 29 (29 binary, 0 integer, 0 implicit integer, 0 continuous)
\ Constraints : 4
\ Obj. scale : 0.2
\ Obj. offset : 0
Minimize
Obj: -3 t_y1 -2 t_y2 -2 t_y3 -3 t_y4 -3 t_y5 -2 t_y6 -2 t_y7 -2 t_y8 -1 t_y9 -2 t_y10 -1 t_y11 -1 t_y12
-2 t_y13 -2 t_y15 -2 t_y16 -2 t_y17 -3 t_y18 -3 t_y20 -1 t_y22 -3 t_y23 -1 t_y24 -2 t_y25 -3 t_y26
-2 t_y28 +1 t_t1_20 +1 t_t9_23 +1 t_t13_16
Subject to
cR_2: +8 t_y1 +7 t_y2 +1 t_y3 +13 t_y4 +8 t_y5 +2 t_y6 +1 t_y7 +1 t_y8 +2 t_y9 +4 t_y10 +1 t_y11 +1 t_y12
+6 t_y13 +3 t_y14 +7 t_y15 +3 t_y16 +10 t_y17 +10 t_y18 +8 t_y20 +10 t_y21 +4 t_y22 +1 t_y23 +8 t_y24
+1 t_y25 +7 t_y26 +6 t_y28 <= +17
sum2: -1 t_y1 -1 t_y2 -1 t_y3 -1 t_y4 -1 t_y5 -1 t_y6 -1 t_y7 -1 t_y8 -1 t_y9 -1 t_y10 -1 t_y11 -1 t_y12
-1 t_y13 -1 t_y14 -1 t_y15 -1 t_y16 -1 t_y17 -1 t_y18 -1 t_y20 -1 t_y21 -1 t_y22 -1 t_y23 -1 t_y24 -1 t_y25
-1 t_y26 -1 t_y28 <= -2
cR_0: +3 t_y1 +4 t_y2 +5 t_y3 +6 t_y4 +4 t_y5 +10 t_y6 +3 t_y7 +2 t_y8 +4 t_y9 +3 t_y10 +3 t_y11 +2 t_y12
+4 t_y13 +2 t_y14 +9 t_y15 +6 t_y16 +2 t_y17 +7 t_y18 +6 t_y20 +3 t_y21 +1 t_y22 +7 t_y23 +4 t_y24 +8 t_y25
+10 t_y26 +6 t_y28 <= +15
cR_3: +6 t_y1 +4 t_y2 +7 t_y3 +9 t_y4 +3 t_y5 +5 t_y6 +5 t_y7 +2 t_y8 +3 t_y9 +8 t_y10 +4 t_y11 +1 t_y12
+10 t_y13 +9 t_y14 +10 t_y15 +1 t_y16 +9 t_y17 +5 t_y18 +9 t_y20 +2 t_y21 +6 t_y22 +3 t_y23 +4 t_y24
+7 t_y25 +2 t_y26 +10 t_y28 <= +16
Bounds
0 <= t_y1 <= 0
0 <= t_y2 <= 0
0 <= t_y3 <= 0
0 <= t_y4 <= 0
0 <= t_y5 <= 0
0 <= t_y6 <= 0
1 <= t_y7 <= 1
0 <= t_y8 <= 0
0 <= t_y9 <= 0
0 <= t_y10 <= 0
0 <= t_y11 <= 0
0 <= t_y12 <= 0
0 <= t_y13 <= 0
0 <= t_y14 <= 0
0 <= t_y15 <= 0
0 <= t_y16 <= 0
1 <= t_y17 <= 1
0 <= t_y18 <= 0
0 <= t_y20 <= 0
0 <= t_y21 <= 0
0 <= t_y22 <= 0
0 <= t_y23 <= 0
0 <= t_y24 <= 0
0 <= t_y25 <= 0
1 <= t_y26 <= 1
0 <= t_y28 <= 0
0 <= t_t1_20 <= 0
0 <= t_t9_23 <= 0
0 <= t_t13_16 <= 0
Binaries
t_y1 t_y2 t_y3 t_y4 t_y5 t_y6 t_y7 t_y8 t_y9 t_y10 t_y11 t_y12 t_y13 t_y14 t_y15 t_y16 t_y17 t_y18 t_y20
t_y21 t_y22 t_y23 t_y24 t_y25 t_y26 t_y28 t_t1_20 t_t9_23 t_t13_16
End
More information about the Scip
mailing list