[SCIP] Branch-and-Cut - SCIP says that solution is optimal, but its not
Matheus Ota
matheusota at gmail.com
Thu Nov 28 18:49:50 CET 2019
Hi Gregor,
sorry to hear you are facing trouble. Does SCIP find the correct solution
> if you disable your custom cutting planes?
>
I believe this is not possible. I'm not sure if this is how it is called in
SCIP, but some of the constraints added by this constraint handler are
"lazy constraints". In other words, they are constraints that are needed to
correctly describe the problem. Some of the constraints are just "user
cuts", I use them just to get better bounds. Probably I should separate
these into two constraint handlers afterwards...
If not, in order to get to the bottom of this issue, please pass the 3073
> solution as a debug solution to SCIP. Please see the last section of
> https://scip.zib.de/doc/html/DEBUG.php for instructions about how to
> recompile SCIP to enable debug solutions.
> With a debug solution, SCIP crashes as soon as a bound change/cut/conflict
> is found that renders this solution infeasible, pretty much like your
> script.
>
Very nice to know this Debug Solution feature, thanks! I did what you said
and got the following result.
> SCIP using Gurobi 8.1.0
> Academic license - for non-commercial use only
> feasible solution found by trivial heuristic after 0.0 seconds, objective
> value 0.000000e+00
> presolving:
> ***** debug: reading solution file <tmp/cut_val.txt>
> ***** debug: read 50 non-zero entries (50 variables found)
> (round 1, fast) 25 del vars, 25 del conss, 0 add conss, 0 chg
> bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
> (round 2, exhaustive) 25 del vars, 25 del conss, 0 add conss, 0 chg
> bounds, 0 chg sides, 0 chg coeffs, 1 upgd conss, 0 impls, 0 clqs
> (0.0s) probing cycle finished: starting next cycle
> presolving (3 rounds: 3 fast, 2 medium, 2 exhaustive):
> 25 deleted vars, 25 deleted constraints, 0 added constraints, 0 tightened
> bounds, 0 added holes, 0 changed sides, 0 changed coefficients
> 0 implications, 0 cliques
> presolved problem has 25 variables (25 bin, 0 int, 0 impl, 0 cont) and 2
> constraints
> 1 constraints of type <BCP Cuts>
> 1 constraints of type <knapsack>
> transformed objective value is always integral (scale: 1)
> Presolving Time: 0.00
> transformed 1/1 original solutions to the transformed problem space
>
> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols
> |rows |cuts |confs|strbr| dualbound | primalbound | gap
> 0.0s| 1 | 0 | 0 | - | 754k| 0 | 0 | 25 | 2 | 25
> | 0 | 0 | 0 | 0 | 3.073000e+03 | 0.000000e+00 | Inf
> 0.0s| 1 | 0 | 1 | - | 756k| 0 | 1 | 25 | 2 | 25
> | 1 | 1 | 0 | 0 | 3.073000e+03 | 0.000000e+00 | Inf
> R: x_24,0 + x_23,1 + x_21,0 + x_14,1 <= 3
> R: x_23,1 + x_21,0 + x_20,1 + x_19,0 <= 3
> R: x_24,0 + x_23,1 + x_15,0 + x_14,1 <= 3
> R: x_23,1 + x_21,0 + x_10,1 + x_19,0 <= 3
> R: x_24,0 + x_23,1 + x_5,0 + x_14,1 <= 3
> R: x_23,1 + x_21,0 + x_0,1 + x_19,0 <= 3
> R: x_23,1 + x_21,0 + x_1,1 + x_19,0 <= 3
> R: x_23,1 + x_21,0 + x_2,1 + x_19,0 <= 3
> R: x_23,1 + x_21,0 + x_3,1 + x_19,0 <= 3
> R: x_24,0 + x_23,1 + x_4,0 + x_14,1 <= 3
> ***** debug: row <face cut> violates debugging solution (lhs=-1e+20,
> rhs=3, activity=[4,4], local=0, lpfeastol=1e-06)
> face cut: -1e+20 <= -1<t_x_24,1> +2<t_x_23,1> +1<t_x_14,1> -1<t_x_4,1> +2
> <= 3
>
The prints that starts with "R:" are made by my code. I have some
constraints in my model of the type:
x_a,0 + x_a,1 = 1 (*)
Thus, replacing (*) at the constraint x_24,0 + x_23,1 + x_4,0 + x_14,1 <=
3, I get:
=> (1 - x_24,1) + x_23,1 + (1 - x_4,1) + x_14,1 = -x_24,1 + x_23,1 - x_4,1
+ x_14,1 + 2 <= 3
Which is similar to the constraint SCIP reports:
=> face cut: -1e+20 <= -1<t_x_24,1> +2<t_x_23,1> +1<t_x_14,1> -1<t_x_4,1>
+2 <= 3
But it seems SCIP erroneously lifted the coefficient for x_23,1.
Do you have any thoughts on this issue?
Also, is it possible for me to deactivate all default SCIP cuts? For
purposes of testing, I want to use only the cuts made by my constraint
handler.
Thanks,
Matheus
Em qui., 28 de nov. de 2019 às 04:59, Gregor Hendel <hendel at zib.de>
escreveu:
> Dear Matheus,
>
> sorry to hear you are facing trouble. Does SCIP find the correct solution
> if you disable your custom cutting planes?
>
> If not, in order to get to the bottom of this issue, please pass the 3073
> solution as a debug solution to SCIP. Please see the last section of
> https://scip.zib.de/doc/html/DEBUG.php for instructions about how to
> recompile SCIP to enable debug solutions.
>
> With a debug solution, SCIP crashes as soon as a bound change/cut/conflict
> is found that renders this solution infeasible, pretty much like your
> script.
>
> Let us know what causes this issue for you,
> Gregor
>
> Am 28.11.19 um 03:51 schrieb Matheus Ota:
>
> Hello all,
>
> My name is Matheus, I implementing a Branch-and-Cut using SCIP for a
> problem that I'm currently working on in my masters. In order to do so, I
> implemented a custom Constraint Handler, and the LP solver that I'm using
> with SCIP is Gurobi 8.1.
>
> The objective function of my problem is of the maximization type. I
> actually already implemented the same model on Gurobi and I'm trying SCIP
> because I want to add multiple cuts per node of the Branch-and-Bound tree,
> and this is not possible with Gurobi. My Gurobi model returns an optimal
> solution with an objective function value of 3073. I manually checked this
> solution and it is ok. But the SCIP version says that a solution with value
> 3056 is optimal. This is the log:
>
> SCIP using Gurobi 8.1.0
>> Academic license - for non-commercial use only
>> feasible solution found by trivial heuristic after 0.0 seconds, objective
>> value 0.000000e+00
>> presolving:
>> (round 1, fast) 25 del vars, 25 del conss, 0 add conss, 0 chg
>> bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
>> (round 2, exhaustive) 25 del vars, 25 del conss, 0 add conss, 0 chg
>> bounds, 0 chg sides, 0 chg coeffs, 1 upgd conss, 0 impls, 0 clqs
>> (0.0s) probing cycle finished: starting next cycle
>> presolving (3 rounds: 3 fast, 2 medium, 2 exhaustive):
>> 25 deleted vars, 25 deleted constraints, 0 added constraints, 0
>> tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
>> 0 implications, 0 cliques
>> presolved problem has 25 variables (25 bin, 0 int, 0 impl, 0 cont) and 2
>> constraints
>> 1 constraints of type <BCP Cuts>
>> 1 constraints of type <knapsack>
>> transformed objective value is always integral (scale: 1)
>> Presolving Time: 0.00
>> transformed 1/1 original solutions to the transformed problem space
>>
>> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols
>> |rows |cuts |confs|strbr| dualbound | primalbound | gap
>> 0.0s| 1 | 0 | 0 | - | 754k| 0 | 0 | 25 | 2 | 25
>> | 0 | 0 | 0 | 0 | 3.073000e+03 | 0.000000e+00 | Inf
>> 0.0s| 1 | 0 | 1 | - | 756k| 0 | 1 | 25 | 2 | 25
>> | 1 | 1 | 0 | 0 | 3.073000e+03 | 0.000000e+00 | Inf
>> 0.0s| 1 | 0 | 18 | - | 783k| 0 | 12 | 25 | 2 | 25
>> | 21 | 21 | 0 | 0 | 3.073000e+03 | 0.000000e+00 | Inf
>> 0.0s| 1 | 2 | 18 | - | 801k| 0 | 12 | 25 | 2 | 25
>> | 21 | 21 | 0 | 12 | 3.073000e+03 | 0.000000e+00 | Inf
>> R 0.1s| 2 | 1 | 48 | 30.0 | 820k| 1 | 1 | 25 | 2 | 25
>> | 47 | 47 | 0 | 12 | 3.073000e+03 | 2.975000e+03 | 3.29%
>> R 0.1s| 4 | 3 | 96 | 26.0 | 854k| 3 | 2 | 25 | 2 | 25
>> | 81 | 81 | 0 | 12 | 3.073000e+03 | 3.056000e+03 | 0.56%
>>
>> SCIP Status : problem is solved [optimal solution found]
>> Solving Time (sec) : 0.18
>> Solving Nodes : 31
>> Primal Bound : +3.05600000000000e+03 (8 solutions)
>> Dual Bound : +3.05600000000000e+03
>> Gap : 0.00 %
>>
>
> Since it says the gap is 0%, I guess the problem here is not the gap
> tolerance.
> In my implementation I'm including the default plugins
> (SCIPincludeDefaultPlugins), and the only parameters that I'm changing are
> the threads (lp/threads = 4) and the absolute gap (limits/absgap = 1 -
> 1e-6), since I know the objective value should be an integer. I also
> already implemented the CONSLOCK method in my constraint handler, so that
> the presolve doesnt round the variables.
>
> When executing with the LP info (display/lpinfo = true), these are the
> last lines in the log.
>
>> adding cuts
>> x_24,0 + x_1,1 + x_2,0 + x_19,1 <= 3
>> x_24,0 + x_1,1 + x_3,0 + x_19,1 <= 3
>> R: x_24,0 + x_3,0 - x_8,0 - x_7,0 - x_4,0 - x_1,0 <= 1
>> Optimize a model with 191 rows, 25 columns and 1033 nonzeros
>> Coefficient statistics:
>> Matrix range [1e+00, 5e+02]
>> Objective range [3e+01, 5e+02]
>> Bounds range [1e+00, 1e+00]
>> RHS range [1e+00, 3e+03]
>> Iteration Objective Primal Inf. Dual Inf. Time
>> 0 3.0730000e+03 4.000000e+01 0.000000e+00 0s
>>
>> Solved in 15 iterations and 0.00 seconds
>> Infeasible model
>> Optimize a model with 191 rows, 25 columns and 1033 nonzeros
>> Coefficient statistics:
>> Matrix range [1e+00, 5e+02]
>> Objective range [3e+01, 5e+02]
>> Bounds range [1e+00, 1e+00]
>> RHS range [1e+00, 3e+03]
>> 0 3.0730000e+03 6.105000e+01 0.000000e+00 0s
>>
>> Solved in 17 iterations and 0.00 seconds
>> Infeasible model
>>
>> SCIP Status : problem is solved [optimal solution found]
>> Solving Time (sec) : 0.19
>> Solving Nodes : 31
>> Primal Bound : +3.05600000000000e+03 (8 solutions)
>> Dual Bound : +3.05600000000000e+03
>> Gap : 0.00 %
>> check feasibility
>> is feasible
>>
>
> I added some custom prints ("add cuts" and "check feasibility"). It seems
> that the solution with value 3073 is getting "cut out" of the polytope.
> I have a script that gets a solution and checks if a set of inequalities
> is violated or not. No constraint added by my constraint handler is being
> violated by the 3073 solution.
> Is it possible that SCIP is adding cuts that is cutting more than needed?
> Can you please help me with this problem? Any ideas are welcome!
>
> Thanks!
> Matheus
>
> _______________________________________________
> Scip mailing listScip at zib.dehttps://listserv.zib.de/mailman/listinfo/scip
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20191128/2809530e/attachment.html>
More information about the Scip
mailing list