[SCIP] Branch-and-Cut - SCIP says that solution is optimal, but its not
Gerald Gamrath
gamrath at zib.de
Fri Nov 29 16:59:57 CET 2019
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
> https://listserv.zib.de/mailman/listinfo/scip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20191129/2c95b76a/attachment.html>
More information about the Scip
mailing list