JuMP/CPLEX: seemingly not all lazy cuts are respected

Specific Domains Optimization (Mathematical)
1

Dear folks,
it seems that CPLEX sometimes does not respect all lazy cuts in the final solution. I know that there is no guarantee that it respects submitted cuts immediately, but it should do in the final solution afaik. Unfortunately, I am not able to produce an MWE for what I observe:
I try to solve an ILP in which I add computationally expensive lazy cuts in a solver-specific callback. Thus, I want to avoid generating an already known cut for a candidate solution. In the callback I do something like:

if cut_already_submitted_for_current_candidate_solution
  return     #"early-exit"
end
construct_and_submit_cut()
return

because CPLEX frequently suggests one-and-the-same candidate solution. Thus, without the “early-exit” in the if-statement, one-and-the-same cut might be generated and submitted more than once, in which case the solutions are always correct. However, with the “early-exit”, sometimes seemingly not all cuts are respected in the final solution - for some reason I do not know.
As a workaround, I created a copy of my initial model and pass it to my callback function. Whenever I submit a LazyConstraint() to the initial model, I also add it as @constraint() to the copied model. Finally, after solving the branch-and-cut (with “early-exit”) for the initial model, I solve the (compact) copied model and obtain the expected solution.

Note: in case the objective value of my initial model is wrong, it is always lower than it should be (because I solve a minimization problem whose objective value is pushed up by the lazy constraints).
Further note: I also tried to set the option CPX_USECUT_FORCE which did not help.

I tried different versions CPLEX 12.10 - 22.1. Moreover, I use JuMP v1.9.0, CPLEX.jl v0.9.7, MathOptInterface v1.13.1, and Julia 1.8.5.

Do you have any ideas why this strange behavior appears sometimes? Many thanks in advance.

1 Like
2

The early exit is wrong. If cplex asks for the same point you need to give the cut again.

This can happen for a number of reasons.

To avoid recomputing, cache the cuts in a dictionary mapping point to cut.

2 Likes
3

I’ve opened a PR to improve our documentation of this: [docs] clarify lazy constraint revisiting point by odow · Pull Request #3278 · jump-dev/JuMP.jl · GitHub

1 Like
4

Thanks @odow. One thing is to remark: always re-adding a cut early if I already know it for a candidate point does not work. It works, however, if I only re-add it early if it is currently violated.

1 Like
5

This is mentioned in the docs Solver-independent Callbacks · JuMP.

Solver callbacks have a very particular set of assumptions that you must not violate.

1 Like