[SCIP] Branch-and-Cut - SCIP says that solution is optimal, but its not
Gregor Hendel
hendel at zib.de
Fri Nov 29 21:16:19 CET 2019
Dear Matheus,
Please start by modifying the parameters
separating/maxstallrounds = k and separating/maxstallroundsroot = m
to your needs, which will stop the separation after k/m separation
rounds with no improvement in the dual bound.
If you check how stalling is detected in the function
src/scip/solve.c:priceAndCutLoop, you can modify the relative comparison
between two successive LP values, where we currently use a hard coded
constant 1e-4.
Have a nice weekend,
Gregor
Am 29.11.19 um 20:35 schrieb Matheus Ota:
> 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
> <mailto: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 <mailto: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 <mailto: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 list
>>> Scip at zib.de <mailto:Scip at zib.de>
>>> https://listserv.zib.de/mailman/listinfo/scip
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de <mailto:Scip at zib.de>
>> https://listserv.zib.de/mailman/listinfo/scip
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de <mailto:Scip at zib.de>
>> https://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/733df479/attachment.html>
More information about the Scip
mailing list