<div dir="ltr"><div>Hi Gregor,</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div>sorry to hear you are facing trouble. Does SCIP find the correct
solution if you disable your custom cutting planes?</div></blockquote><div>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...<br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div>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 <a href="https://scip.zib.de/doc/html/DEBUG.php" target="_blank">https://scip.zib.de/doc/html/DEBUG.php</a> for instructions
about how to recompile SCIP to enable debug solutions.<br>
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.</div></blockquote><div> </div><div>Very nice to know this Debug Solution feature, thanks! I did what you said and got the following result.</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div>SCIP using Gurobi 8.1.0<br>Academic license - for non-commercial use only<br>feasible solution found by trivial heuristic after 0.0 seconds, objective value 0.000000e+00<br>presolving:<br>***** debug: reading solution file <tmp/cut_val.txt><br>***** debug: read 50 non-zero entries (50 variables found)<br>(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<br>(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<br> (0.0s) probing cycle finished: starting next cycle<br>presolving (3 rounds: 3 fast, 2 medium, 2 exhaustive):<br> 25 deleted vars, 25 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients<br> 0 implications, 0 cliques<br>presolved problem has 25 variables (25 bin, 0 int, 0 impl, 0 cont) and 2 constraints<br> 1 constraints of type <BCP Cuts><br> 1 constraints of type <knapsack><br>transformed objective value is always integral (scale: 1)<br>Presolving Time: 0.00<br>transformed 1/1 original solutions to the transformed problem space<br><br> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap <br> 0.0s| 1 | 0 | 0 | - | 754k| 0 | 0 | 25 | 2 | 25 | 0 | 0 | 0 | 0 | 3.073000e+03 | 0.000000e+00 | Inf <br> 0.0s| 1 | 0 | 1 | - | 756k| 0 | 1 | 25 | 2 | 25 | 1 | 1 | 0 | 0 | 3.073000e+03 | 0.000000e+00 | Inf <br> R: x_24,0 + x_23,1 + x_21,0 + x_14,1 <= 3<br> R: x_23,1 + x_21,0 + x_20,1 + x_19,0 <= 3<br> R: x_24,0 + x_23,1 + x_15,0 + x_14,1 <= 3<br> R: x_23,1 + x_21,0 + x_10,1 + x_19,0 <= 3<br> R: x_24,0 + x_23,1 + x_5,0 + x_14,1 <= 3<br> R: x_23,1 + x_21,0 + x_0,1 + x_19,0 <= 3<br> R: x_23,1 + x_21,0 + x_1,1 + x_19,0 <= 3<br> R: x_23,1 + x_21,0 + x_2,1 + x_19,0 <= 3<br> R: x_23,1 + x_21,0 + x_3,1 + x_19,0 <= 3<br> R: x_24,0 + x_23,1 + x_4,0 + x_14,1 <= 3<br>***** debug: row <face cut> violates debugging solution (lhs=-1e+20, rhs=3, activity=[4,4], local=0, lpfeastol=1e-06)<br>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<br></div></blockquote><div><br></div><div>The prints that starts with "R:" are made by my code. I have some constraints in my model of the type:</div><div>x_a,0 + x_a,1 = 1 (*)<br></div><div><br></div><div>Thus, replacing (*) at the constraint x_24,0 + x_23,1 + x_4,0 + x_14,1 <= 3, I get:</div><div> => (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</div><div>Which is similar to the constraint SCIP reports:</div><div> => 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</div><div>But it seems SCIP erroneously lifted the coefficient for x_23,1.</div><div><br></div><div>Do you have any thoughts on this issue?</div><div><br></div><div>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.</div><div><br></div><div>Thanks,</div><div>Matheus<br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Em qui., 28 de nov. de 2019 às 04:59, Gregor Hendel <<a href="mailto:hendel@zib.de">hendel@zib.de</a>> escreveu:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div>
Dear Matheus,<br>
<br>
sorry to hear you are facing trouble. Does SCIP find the correct
solution if you disable your custom cutting planes?<br>
<br>
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 <a href="https://scip.zib.de/doc/html/DEBUG.php" target="_blank">https://scip.zib.de/doc/html/DEBUG.php</a> for instructions
about how to recompile SCIP to enable debug solutions.<br>
<br>
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.<br>
<br>
Let us know what causes this issue for you,<br>
Gregor<br>
<br>
<div>Am 28.11.19 um 03:51 schrieb Matheus
Ota:<br>
</div>
<blockquote type="cite">
<div dir="ltr">
<div>Hello all,</div>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>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:</div>
<div><br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div>SCIP using Gurobi 8.1.0<br>
Academic license - for non-commercial use only<br>
feasible solution found by trivial heuristic after 0.0
seconds, objective value 0.000000e+00<br>
presolving:<br>
(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<br>
(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<br>
(0.0s) probing cycle finished: starting next cycle<br>
presolving (3 rounds: 3 fast, 2 medium, 2 exhaustive):<br>
25 deleted vars, 25 deleted constraints, 0 added
constraints, 0 tightened bounds, 0 added holes, 0 changed
sides, 0 changed coefficients<br>
0 implications, 0 cliques<br>
presolved problem has 25 variables (25 bin, 0 int, 0 impl, 0
cont) and 2 constraints<br>
1 constraints of type <BCP Cuts><br>
1 constraints of type <knapsack><br>
transformed objective value is always integral (scale: 1)<br>
Presolving Time: 0.00<br>
transformed 1/1 original solutions to the transformed
problem space<br>
<br>
time | node | left |LP iter|LP it/n| mem |mdpt |frac
|vars |cons |cols |rows |cuts |confs|strbr| dualbound |
primalbound | gap <br>
0.0s| 1 | 0 | 0 | - | 754k| 0 | 0 |
25 | 2 | 25 | 0 | 0 | 0 | 0 | 3.073000e+03 |
0.000000e+00 | Inf <br>
0.0s| 1 | 0 | 1 | - | 756k| 0 | 1 |
25 | 2 | 25 | 1 | 1 | 0 | 0 | 3.073000e+03 |
0.000000e+00 | Inf <br>
0.0s| 1 | 0 | 18 | - | 783k| 0 | 12 |
25 | 2 | 25 | 21 | 21 | 0 | 0 | 3.073000e+03 |
0.000000e+00 | Inf <br>
0.0s| 1 | 2 | 18 | - | 801k| 0 | 12 |
25 | 2 | 25 | 21 | 21 | 0 | 12 | 3.073000e+03 |
0.000000e+00 | Inf <br>
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%<br>
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%<br>
<br>
SCIP Status : problem is solved [optimal solution
found]<br>
Solving Time (sec) : 0.18<br>
Solving Nodes : 31<br>
Primal Bound : +3.05600000000000e+03 (8 solutions)<br>
Dual Bound : +3.05600000000000e+03<br>
Gap : 0.00 %<br>
</div>
</blockquote>
<div> </div>
<div>Since it says the gap is 0%, I guess the problem here is
not the gap tolerance.</div>
<div>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.</div>
<div><br>
</div>
<div>When executing with the LP info (display/lpinfo = true),
these are the last lines in the log.</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div>adding cuts<br>
x_24,0 + x_1,1 + x_2,0 + x_19,1 <= 3<br>
x_24,0 + x_1,1 + x_3,0 + x_19,1 <= 3<br>
R: x_24,0 + x_3,0 - x_8,0 - x_7,0 - x_4,0 - x_1,0 <= 1<br>
Optimize a model with 191 rows, 25 columns and 1033 nonzeros<br>
Coefficient statistics:<br>
Matrix range [1e+00, 5e+02]<br>
Objective range [3e+01, 5e+02]<br>
Bounds range [1e+00, 1e+00]<br>
RHS range [1e+00, 3e+03]<br>
Iteration Objective Primal Inf. Dual Inf.
Time<br>
0 3.0730000e+03 4.000000e+01 0.000000e+00
0s<br>
<br>
Solved in 15 iterations and 0.00 seconds<br>
Infeasible model<br>
Optimize a model with 191 rows, 25 columns and 1033 nonzeros<br>
Coefficient statistics:<br>
Matrix range [1e+00, 5e+02]<br>
Objective range [3e+01, 5e+02]<br>
Bounds range [1e+00, 1e+00]<br>
RHS range [1e+00, 3e+03]<br>
0 3.0730000e+03 6.105000e+01 0.000000e+00
0s<br>
<br>
Solved in 17 iterations and 0.00 seconds<br>
Infeasible model<br>
<br>
SCIP Status : problem is solved [optimal solution
found]<br>
Solving Time (sec) : 0.19<br>
Solving Nodes : 31<br>
Primal Bound : +3.05600000000000e+03 (8 solutions)<br>
Dual Bound : +3.05600000000000e+03<br>
Gap : 0.00 %<br>
check feasibility<br>
is feasible<br>
</div>
</blockquote>
<div><br>
</div>
<div>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.</div>
<div>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.</div>
<div>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!</div>
<div><br>
</div>
<div>Thanks!</div>
<div>Matheus<br>
</div>
</div>
<br>
<fieldset></fieldset>
<pre>_______________________________________________
Scip mailing list
<a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a>
<a href="https://listserv.zib.de/mailman/listinfo/scip" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a>
</pre>
</blockquote>
<br>
</div>
_______________________________________________<br>
Scip mailing list<br>
<a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a><br>
<a href="https://listserv.zib.de/mailman/listinfo/scip" rel="noreferrer" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a><br>
</blockquote></div>