Using Callbacks for Column-and-constraint generation algorithm

Answered

Angelos Georghiou

• June 21, 2019 14:39

Hi,

I am implementing a column-and-constraint 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

 

 

0

• 

  Daniel Espinoza

  • June 21, 2019 16:33

  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

  0
• 

  Angelos Georghiou

  • June 25, 2019 14:26
  • Edited

  

  

  

  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 pre-solve 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 re-introduce them? Or Gurobi will complain that the constraint contains decisions that don't appear in the problem (because they got eliminated during pre-solve)?

  kind regards,

  Angelos 

  0
• 

  Daniel Espinoza

  • June 26, 2019 12:34

  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

  0
• 

  Angelos Georghiou

  • June 27, 2019 09:09

  

  

  

  Thanks a lot Daniel

  best wishes,

  Angelos

  0

Please sign in to leave a comment.