Lazy constraint generation only when close to optimal solution (Python interface)

[Curtiss Luong]

Hi all,

I am trying to solve a problem using constraint generation with gurobi and python. We are using model.cbLazy in a callback to cut out incumbent solutions as necessary. However, we are attempting to construct an algorithm that does not start verifying incumbent solutions until the gap for the problem is smaller than some threshold "beta". Unfortunately, sometimes, the gap jumps from much larger than "beta" to zero without allowing us to insert a lazy constraint through model.cbLazy, meaning that the optimization terminates without verifying if the current optimal solution is indeed feasible to the overall problem.

We were wondering if there was any way to inject a constraint using model.cbLazy right before the optimization ends (we tried using both MIPNode and MIPSol, but both callback codes seem not to be granular enough), or if there is a way to introduce a constraint and then resume the optimization without losing all of the information from the first run. I notice that if I resume the optimization without introducing an additional constraint, it continues the same optimization with the old branch and cut tree, whereas if I try to use model.addConstraint to add additional constraints it loses a lot of information.

I hope that this is clear enough,
thanks in advance for the help!
Curtiss L

[Renan Garcia]

Curtiss,

> However, we are attempting to construct an algorithm that does not start verifying incumbent solutions until the gap for the problem is smaller than some threshold "beta". Unfortunately, sometimes, the gap jumps from much larger than "beta" to zero without allowing us to insert a lazy constraint through model.cbLazy, meaning that the optimization terminates without verifying if the current optimal solution is indeed feasible to the overall problem.

Gurobi will give you the opportunity to cut off each potential incumbent solution only once. Each time a new incumbent is discovered during the algorithm, the callback function will execute with where=MIPSOL. This is your one and only chance to cut off that particular solution. If you don't, then Gurobi will assume that solution is verified, and the Incumbent bound will improve, causing the gap to jump.

> We were wondering if there was any way to inject a constraint using model.cbLazy right before the optimization ends

If the algorithm worked this way, then it would result in a total enumeration of all feasible (without lazy cuts) solutions. Pruning due to integrality and infeasibility would still be possible, but pruning due to bounds (which is where the real speedup comes from) would not. The algorithm couldn't rely on any of the solutions it found along the way to provide a true bound because they have not been verified. In other words, there would be no gap. And any speedups you saw from a smaller LP with less cuts in it, would be outweighed by the increased number of branch and cut nodes you'd need to explore.

> if there is a way to introduce a constraint and then resume the optimization without losing all of the information from the first run.

No. The old branch and cut tree is discarded whenever you add additional constraints.

Renan

[Curtiss Luong]

Makes sense, thanks!