[SCIP] Constraint handler <linear> detects infeasibility of feasible problem
Kamp, Dominik
Dominik.Kamp at uni-bayreuth.de
Tue Jun 21 16:02:03 CEST 2022
Dear SCIP developers,
some time ago I have submitted a bug report including a possible bugfix, but have not received an answer yet, so I try again on this way now.
If I solve the model Demo.lp given by
Minimize
obj: +1 a_1 +1 a_2 +1 a_3 +1 a_4
Subject To
t_1: +1 x_1 +1 d_1 = +3
t_2: +1 x_2 +1 d_2 -1 s_1 = +0
i_1: +1 d_1 -1 s_1 = +0
e_1: +1 d_2 <= +1
h_1: +1 a_1 -1 y_1 + 1 x_1 = +0
h_2: +1 a_2 -1 y_2 + 1 x_2 = +0
h_3: +8 a_3 -8 y_1 +11 x_1 = +0
h_4: +8 a_4 -8 y_2 +13 x_2 = +0
Bounds
0 <= s_1 <= 3
General
x_1 x_2 y_1 y_2
End
with SCIP 7.0.3 or 8.0.0 using default settings, it says that
constraint handler <linear> detected infeasibility
during presolving, although actually there is the unique optimal solution
objective value: 1.25
x_1 2 (obj:0)
y_1 3 (obj:0)
a_3 0.25 (obj:1)
d_1 1 (obj:0)
a_1 1 (obj:1)
d_2 1 (obj:0)
s_1 1 (obj:0)
After some research I realized that the conclusion of infeasibility in the dualpresolving method of constraint handler <linear> is valid and the issue is rather caused by an infeasible reduction in the MILP presolver as shown below for version 8.0.0.
Output of MILP presolver:
starting presolve of problem Demo.lp:
rows: 5
columns: 6
int. columns: 6
cont. columns: 0
nonzeros: 12
round 0 ( Trivial ): 0 del cols, 0 del rows, 0 chg bounds, 0 chg sides, 0 chg coeffs, 0 tsx applied, 0 tsx conflicts
round 1 (Exhaustive): 2 del cols, 2 del rows, 0 chg bounds, 0 chg sides, 12 chg coeffs, 2 tsx applied, 0 tsx conflicts
round 2 ( Final ): Unchanged
presolved 2 rounds: 2 del cols, 2 del rows, 0 chg bounds, 0 chg sides, 12 chg coeffs, 2 tsx applied, 0 tsx conflicts
presolver nb calls success calls(%) nb transactions tsx applied(%) execution time(s)
colsingleton 2 0.0 0 0.0 0.000
coefftightening 2 0.0 0 0.0 0.000
propagation 2 0.0 0 0.0 0.000
simpleprobing 1 0.0 0 0.0 0.000
parallelrows 1 0.0 0 0.0 0.000
stuffing 1 0.0 0 0.0 0.000
dualfix 1 0.0 0 0.0 0.000
fixcontinuous 0 0.0 0 0.0 0.000
simplifyineq 1 0.0 0 0.0 0.000
doubletoneq 1 0.0 0 0.0 0.000
implint 0 0.0 0 0.0 0.000
dualinfer 0 0.0 0 0.0 0.000
probing 1 0.0 0 0.0 0.000
domcol 1 0.0 0 0.0 0.000
substitution 2 50.0 2 100.0 0.000
reduced problem:
reduced rows: 3
reduced columns: 4
reduced int. columns: 4
reduced cont. columns: 0
reduced nonzeros: 6
Problem before MILP presolver:
STATISTICS
Problem name : t_Demo.lp
Variables : 6 (0 binary, 4 integer, 2 implicit integer, 0 continuous)
Constraints : 0 initial, 8 maximal
OBJECTIVE
Sense : minimize
VARIABLES
[integer] <t_x_1>: obj=-1.375, global bounds=[-0,3], local bounds=[-0,3]
[integer] <t_x_2>: obj=-1.625, global bounds=[-0,3], local bounds=[-0,3]
[integer] <t_y_1>: obj=1, global bounds=[-0,+inf], local bounds=[-0,+inf]
[integer] <t_y_2>: obj=1, global bounds=[-0,+inf], local bounds=[-0,+inf]
[implicit] <t_a_1>: obj=1, global bounds=[0,+inf], local bounds=[0,+inf]
[implicit] <t_a_2>: obj=1, global bounds=[0,+inf], local bounds=[0,+inf]
FIXED
[continuous] <t_d_1>: obj=0, global bounds=[0,3], local bounds=[0,3], aggregated: 3 -1<t_x_1>
[continuous] <t_s_1>: obj=0, global bounds=[0,3], local bounds=[0,3], aggregated: 3 -1<t_x_1>
[continuous] <t_a_3>: obj=0, global bounds=[0,+inf], local bounds=[0,+inf], aggregated: -1.375<t_x_1> +1<t_y_1>
[continuous] <t_a_4>: obj=0, global bounds=[0,+inf], local bounds=[0,+inf], aggregated: -1.625<t_x_2> +1<t_y_2>
[continuous] <t_d_2>: obj=0, global bounds=[0,1], local bounds=[0,1], aggregated: 3 -1<t_x_1> -1<t_x_2>
CONSTRAINTS
[linear] <h_2>: <t_x_2>[I] -<t_y_2>[I] +<t_a_2>[M] == 0;
[linear] <t_2>: 2 <= <t_x_1>[I] +<t_x_2>[I] <= 3;
[linear] <h_3>: +11<t_x_1>[I] -8<t_y_1>[I] <= 0;
[linear] <h_4>: +13<t_x_2>[I] -8<t_y_2>[I] <= 0;
[linear] <h_1>: <t_x_1>[I] -<t_y_1>[I] +<t_a_1>[M] == 0;
END
Problem after MILP presolver:
STATISTICS
Problem name : t_Demo.lp
Variables : 4 (0 binary, 2 integer, 2 implicit integer, 0 continuous)
Constraints : 0 initial, 8 maximal
OBJECTIVE
Sense : minimize
VARIABLES
[integer] <t_x_1>: obj=-0.375, global bounds=[-0,3], local bounds=[-0,3]
[integer] <t_x_2>: obj=-0.625, global bounds=[-0,3], local bounds=[-0,3]
[implicit] <t_a_1>: obj=2, global bounds=[0,+inf], local bounds=[0,+inf]
[implicit] <t_a_2>: obj=2, global bounds=[0,+inf], local bounds=[0,+inf]
FIXED
[continuous] <t_d_1>: obj=0, global bounds=[0,3], local bounds=[0,3], aggregated: 3 -1<t_x_1>
[continuous] <t_s_1>: obj=0, global bounds=[0,3], local bounds=[0,3], aggregated: 3 -1<t_x_1>
[continuous] <t_a_3>: obj=0, global bounds=[0,+inf], local bounds=[0,+inf], aggregated: -0.375<t_x_1> +1<t_a_1>
[continuous] <t_a_4>: obj=0, global bounds=[0,+inf], local bounds=[0,+inf], aggregated: -0.625<t_x_2> +1<t_a_2>
[continuous] <t_d_2>: obj=0, global bounds=[0,1], local bounds=[0,1], aggregated: 3 -1<t_x_1> -1<t_x_2>
[integer] <t_y_1>: obj=0, global bounds=[-0,+inf], local bounds=[-0,+inf], aggregated: +1<t_x_1> +1<t_a_1>
[integer] <t_y_2>: obj=0, global bounds=[-0,+inf], local bounds=[-0,+inf], aggregated: +1<t_x_2> +1<t_a_2>
CONSTRAINTS
[linear] <t_2>: 2 <= <t_x_1>[I] +<t_x_2>[I] <= 3;
[linear] <h_3>: -3<t_x_1>[I] +8<t_a_1>[M] >= -0;
[linear] <h_4>: -5<t_x_2>[I] +8<t_a_2>[M] >= -0;
END
This reduction would be fine, if variables <t_a_1> and <t_a_2> were actual integers. However, in the resulting problem they are still implicit integers though not both of them can be integral in an optimal solution. The reason is that their objective coefficients are positive, and constraint <t_2> implies that either 3/8<t_x_1> or 5/8<t_x_2> is positive and fractional. Consequently, constraint handler <linear> will legitimately aggregate constraints <h_3> and <h_4> by fixing <t_a_1> to 3/8<t_x_1> and <t_a_2> to 5/8<t_x_2> contradicting the integrality of fixed variables <t_y_1> and <t_y_2> by aggregated constraints <h_1> and <h_2>, which is finally detected in the according dualpresolving method of constraint handler <linear>.
So the MILP presolver itself also works fine, but seem to get misleading information on variable types if implicit integers are involved. Therefore, a possible bugfix is to replace line 159 of file presol_milp.cpp
builder.setColIntegral(i, SCIPvarIsIntegral(var));
by
builder.setColIntegral(i, SCIPvarGetType(var) < SCIP_VARTYPE_IMPLINT);
in order to treat implicit integers like continuous variables in the MILP presolver. This prevents infeasible reductions in this and other examples suffering from the same issue.
Please let me know, if this fix makes sense from your experienced perspective. Thank you in advance!
Best regards,
Dominik
More information about the Scip
mailing list