[SCIP] Branch-and-Cut - SCIP says that solution is optimal, but its not

[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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20191127/72c262a1/attachment.html>