[SCIP] Branch-and-Cut - SCIP says that solution is optimal, but its not
Matheus Ota
matheusota at gmail.com
Fri Nov 29 20:35:26 CET 2019
Hi Gerald,
Thanks for the clarifications! In order to avoid a "tailing off" effect in
a node of the Branch-and-Bound tree, I want to check whether the difference
between the value of the current LP "round" and the value of previous the
LP "round" is greater than a parameter. Is there a parameter to do so in
SCIP? Or how could I start to implement this?
Thanks,
Matheus
Em sex., 29 de nov. de 2019 às 12:59, Gerald Gamrath <gamrath at zib.de>
escreveu:
> Hi Matheus,
>
> this is the list of constraint handlers, the only one of those that is
> called during separation (#Separate) and adds cuts (Cuts, Applied) is your
> constraint handler. The other constraint handlers are called for
> enforcement, propagation, and domain propagation, but do not add any cuts.
> You should also check the Separators section of the statistics, there
> should be 0 there everywhere.
>
> Best,
> Gerald
>
> Am 29.11.19 um 16:44 schrieb Matheus Ota:
>
> 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
>>>
>>
> _______________________________________________
> Scip mailing listScip at zib.dehttps://listserv.zib.de/mailman/listinfo/scip
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20191129/c433bd12/attachment.html>
More information about the Scip
mailing list