<div dir="ltr"><div>Hi Gerald,</div><div><br></div><div>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?<br></div><div><br></div><div>Thanks,</div><div>Matheus<br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Em sex., 29 de nov. de 2019 às 12:59, Gerald Gamrath <<a href="mailto:gamrath@zib.de">gamrath@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 bgcolor="#FFFFFF">
Hi Matheus,<br>
<br>
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.<br>
You should also check the Separators section of the statistics,
there should be 0 there everywhere.<br>
<br>
Best,<br>
Gerald<br>
<br>
<div>Am 29.11.19 um 16:44 schrieb Matheus
Ota:<br>
</div>
<blockquote type="cite">
<div dir="ltr">
<div>Hi All,</div>
<div><br>
</div>
<div>My code had a bug, that why the constraint printed by SCIP
was different. My bad.</div>
<div>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:</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>Constraints : Number MaxNumber #Separate
#Propagate #EnfoLP #EnfoRelax #EnfoPS #Check
#ResProp Cutoffs DomReds Cuts Applied
Conss Children<br>
benderslp : 0 0 0
0 50 0 0 44 0
0 0 0 0 0
0<br>
My Cuts : 1 1 101
0 50 0 0 40 0
0 0 746 746 0
0<br>
integral : 0 0 0
0 50 0 0 31 0
0 37 0 0 0
70<br>
knapsack : 1 1 0
907 1 0 0 27 1
0 0 0 0 0
0<br>
setppc : 25 25 0
963 1 0 0 26 24
1 34 0 0 0
0<br>
logicor : 0+ 3 0
3 0 0 0 0 0
0 0 0 0 0
0<br>
benders : 0 0 0
0 1 0 0 27 0
0 0 0 0 0
0<br>
countsols : 0 0 0
0 1 0 0 27 0
0 0 0 0 0
0<br>
components : 0 0 0
0 0 0 0 0 0
0 0 0 0 0
0<br>
</div>
</blockquote>
<div><br>
</div>
<div>And it seems (at least to me) that SCIP is adding more cuts
than mine.</div>
<div><br>
</div>
<div>Thanks,</div>
<div>Matheus<br>
</div>
<div><br>
</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">Em qui., 28 de nov. de 2019 às
14:49, Matheus Ota <<a href="mailto:matheusota@gmail.com" target="_blank">matheusota@gmail.com</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 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" target="_blank">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>
</blockquote>
</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>
</blockquote></div>