A lazy constraint and MIP optimality issue

-

Hi,

I’m implementing a MIP cut generation algorithm on JuMP+Gurobi using MOI.LazyConstraintCallback.

Theoretically, the algorithm is correct. However, running tests on a large batch of instances and cross-checking with another pure MIP, 1 of the runs yields a slightly wrong answer.

I’ve tested the solution by hand and my check does detect the optimal integer point as infeasible, the constraint also cuts it off. But upon closer inspection, it appears that Gurobi accepts it as incumbent without giving me the opportunity to reject it. The call-back function is in fact not called at all, and the program ends.

The final solution does violate my lazy constraint by more than the feasibility tolerance (it’s a knapsack constraint with integer coefficients/RHS)

A particularity(?) of this issue is that this incumbent is within 0.01% of the LB.

Here is a portion of the log :

Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

[...]

 10624   940     cutoff   40       270.35700  270.32800  0.01%  17.7   20s
 17174   989  270.32800   55    1  270.35700  270.32800  0.01%  15.5   25s
 23761  1275     cutoff   41       270.35700  270.32800  0.01%  14.6   30s
 30166  1346  270.32800   44    2  270.35700  270.32800  0.01%  14.0   35s
 36625  1444  270.32800   31    7  270.35700  270.32800  0.01%  13.7   40s
 43289  1411  270.32800   49    3  270.35700  270.32800  0.01%  13.4   45s
 50075  1464  270.32800   36    2  270.35700  270.32800  0.01%  13.2   50s
*51325     2              38     270.3280000  270.32800  0.00%  13.1   50s    # optimal [sic]

The optimal objective value should be 270.357.

Do you have any insights?

Many thanks!

Marouane FELLOUSSI

June 05, 2024 07:31
Edited

Update #1

Disabling solver cuts solves the issue at the expense of runtime (and using all threads as opposed to only 1 before)

After ~100s, the LB is correctly updated to 270.357.

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

[...]

 555629   155  270.32800   63    1  270.35700  270.32800  0.01%  10.3  110s

Optimal solution found (tolerance 1.00e-04)
Best objective 2.703570000000e+02, best bound 2.703570000000e+02, gap 0.0000%

Update #2

It has to do with the number of threads. Running (n > 1)-threaded, with or without solver cuts yields a correct solution.

Update #3

It was a numerical precision issue in the callback, that only becomes apparent on single-threaded runs. Always use tolerance when checking for feasibility, regardless of the number of threads.

A lazy constraint and MIP optimality issue

Comments

Didn't find what you were looking for?