I’m working on a robust optimisation problem wherein I first solve the nominal problem. I then check if the solution obtained from the nominal problem violates the robust constraints for a particular uncertain scenario (lets say the worst case realisation of the uncertain parameters) by solving a separation problem. If so, I add the violated inequality to the nominal problem and resolve. My question is, can I embed the separation problem within the original optimisation problem (just like in simplelazy.jl) and solve it or write a function to solve the separation problem outside the scope of the variables of the problem?
TIA
How about just solving the model once, then adding the new constraint and solving again (with a warm start) in a loop until you can no longer add new constraints? The lazy constraint callback is mainly for MIP problems because the constraint generation needs to be done from within the search tree, where the constraint can be either local to the sub-tree or global, and the user needs access to the intermediate problem state to determine the separation hyperplane, so it’s a more complicated situation than what you might be looking for.
This is something that I did (although not with a warm start) but I just read about callbacks and thought this feature would be good to use for the problem. The convenience of callbacks is that I don’t have to declare a separation problem outside the scope of the variables.
Wrt the callbacks again, I’m solving a MIP and the violated constraint I add to the nominal problem is a global constraint and certainly not limited to a particular node in the BnB tree. Would you still suggest I use the former method than callbacks?
Also, what exactly would happen if I were to use callbacks instead?
It depends on how often you want to generate these constraints. If you want to generate them as soon as you find an integer-feasible solution or even at every feasible node of the tree, integer-feasible or not, then the callbacks are your only way of doing that. If you only want to generate the constraints for the solution of the whole MIP, then the first method is the way to go. Notice that a warm start for a whole MIP also includes adding the best outer bound found (upper for max. and lower for min.) which is basically the objective value of your previous solution. This should reduce the gap between the outer and inner bound and should speed up your search.
I’m guessing that the separation problem shall be called just once. We first solve the nominal problem to optimality, check if the solution violates inequalities (solve separation once), add the violated inequality.
Just one more question. What exactly does the highlighted phrase mean? This is from the JuMP callbacks documentation. And is the current solution mentioned in the phrase referring to the final solution obtained when the MIP is solved to optimality or a solution at one of the nodes?
“Examples include changing branching decisions in branch-and-bound, adding custom cutting planes, providing custom heuristics to find feasible solutions, or implementing on-demand separators to add new constraints only when they are violated by the current solution (also known as lazy constraints).”
That’s referring to the case in our discussion.
The term “cutting planes” in MIP literature is typically used to refer to those separation hyperplanes that separate the current integer-infeasible solution from the integer-feasible solution space with the goal of promoting the integrality of the solution of the continuous relaxation. The same term is also used in convex optimization literature which use piecewise linear approximation of constraints.
More generally however, you may relax some constraints and generate them on demand either because they are too many or infinite, and largely redundant. The term “lazy constraints” or “constraint generation” is used to describe this case.
The current solution here should refer to the node solution.
1 Like
If you want to apply a callback for lazy constraints to a problem that has not integer variables, you might need to add a dummy variable anyway, to trigger the callback mechanism. See the discussion in issue JuMP/#779.
Thank you @mohamed82008 for all your answers.
1 Like
The problem I’m solving is a MIP btw.