Whilst generating lazy constraints through my custom IloCplex.Callback.Function, I encounter the following behaviour:
- After identifying ‘valid’ lazy constraints A, for one candidate X my heuristic cannot identify a violated constraint.
- Before returning the solution X, more candidates Y are explored with better objective values. While these candidates Y are considered, my heuristics do find new constraints B that are added as lazy constraints.
- Taking into considerations these new constraints B, the solver finds out there are no candidate solutions superior to candidate X. Hence, X is returned as the optimal solution.
- However: It turns out that candidate X does not satisfy some of the constraints B that were added after its discovery.
In other words, when we found X, it appeared to be feasible, but given the new lazy constraints B, it turns out not to be and the solver should continue to look for new candidate solutions.
Is there any way to require a solution to satisfy these lazy constraints?
No. There is an implicit contract between a callback and CPLEX saying that if the callback fails to identify a violated lazy constraint, then the solution is feasible. Retroactively applying constraints generated later is not possible. If you tried to implement that, it would cause problems. For instance, between when X was incorrectly accepted and when constraints B were identified, the objective value of X might have been used to prune nodes that, in hindsight, should not be pruned.
Bottom line: a lazy constraint callback MUST identify at least one violated constraint for any candidate solution that is not truly feasible.