<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>