[SCIP] Branch-and-Cut - SCIP says that solution is optimal, but its not
Matheus Ota
matheusota at gmail.com
Fri Nov 29 16:44:11 CET 2019
Hi All,
My code had a bug, that why the constraint printed by SCIP was different.
My bad.
But now I'm still in doubt about how I deactivate all SCIP default cuts.
I'm using SCIPsetSeparating(scip, SCIP_PARAMSETTING_OFF, TRUE). But when I
print the statistics I get:
Constraints : Number MaxNumber #Separate #Propagate #EnfoLP
> #EnfoRelax #EnfoPS #Check #ResProp Cutoffs DomReds
> Cuts Applied Conss Children
> benderslp : 0 0 0 0
> 50 0 0 44 0 0 0
> 0 0 0 0
> My Cuts : 1 1 101 0 50
> 0 0 40 0 0 0
> 746 746 0 0
> integral : 0 0 0 0
> 50 0 0 31 0 0 37
> 0 0 0 70
> knapsack : 1 1 0 907
> 1 0 0 27 1 0 0
> 0 0 0 0
> setppc : 25 25 0 963
> 1 0 0 26 24 1 34
> 0 0 0 0
> logicor : 0+ 3 0 3
> 0 0 0 0 0 0 0
> 0 0 0 0
> benders : 0 0 0 0
> 1 0 0 27 0 0 0
> 0 0 0 0
> countsols : 0 0 0 0
> 1 0 0 27 0 0 0
> 0 0 0 0
> components : 0 0 0 0
> 0 0 0 0 0 0 0
> 0 0 0 0
>
And it seems (at least to me) that SCIP is adding more cuts than mine.
Thanks,
Matheus
Em qui., 28 de nov. de 2019 às 14:49, Matheus Ota <matheusota at gmail.com>
escreveu:
> 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/20191129/dd75bcef/attachment.html>
More information about the Scip
mailing list