Using Callbacks for Columnandconstraint generation algorithm
AnsweredHi,
I am implementing a columnandconstraint generation algorithm. The problem is solved as follows: A relaxed master MILP problem is solved. Using the optimal solution of the master problem, we solve a subproblem to verify if the solution if optimal. If not, a set of constraints is added to the master problem. These constraints contain unique continuous variables that do not affect the rest of the constraints.
Currently, I am solving a sequence of MILPs to optimimality when solving the master problem, which is time consuming. So I would like to explore the option of solving a single MILP and adding these constraints as lazy constraints as needed in the B&B procedure. I have seen the tsp example (see link below), however, in that example only lazy constraints are added without new continuous variables. From what I understand, the class GRBCallback() it does not allow to add new continuous variables. We can only add constraints. Is this correct?
https://www.gurobi.com/documentation/8.1/examples/tsp_cpp_cpp.html
https://www.gurobi.com/documentation/8.1/refman/cpp_grbcallback.html
I could include all continuous variables in the initial MILP. Since they will not appear in any of the constraints (initially) they shouldn't interfere with the complexity of the B&B. However, I want to avoid this, since the size of these continuous variables is exponential with respect to the problem size.
Is there a cleverer way to address this issue.
Thanks for your help
Angelos

Angelos,
No, there is no way to add variables during B&B. You could do a https://en.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_elimination of the new variable....
Hope that helps,
Daniel

Dear Daniel,
Thank you for your suggestion. For now, using Fourier Motzkin elimination is not an option as I need to add many variables and this will be nearly impossible to do.
Let me ask a small follow up question about how Callback works.
Assume that I introduce all continuous variables in my initial Master problem, and say non of them appear in the constraints (as these constraints will be added later on as lazy constraints), then presolve will eliminate them before starting the B&B algorithm. Now, when adding a new constraint as lazy constraint, will Gurobi recognize that it has previous eliminated the continuous variables that appear in the new constraint and reintroduce them? Or Gurobi will complain that the constraint contains decisions that don't appear in the problem (because they got eliminated during presolve)?
kind regards,
Angelos

For using lazy constraints, you have to set the parameter http://www.gurobi.com/documentation/8.1/refman/lazyconstraints.html#parameter:LazyConstraints
which will disable many presolve reductions (because having lazy constraints means that presolve does not know the full problem). So, in principle (with that parameter enabled) it should work.
Daniel
Please sign in to leave a comment.
Comments
4 comments