5

I am working on reducing the solving time of the optimization problem I am working on. One of the ideas I am exploring is the usage of Lazy constraints. As solver, I am using Gurobi, so both pre-enumerated and callback lazy constraints are possible.

In all examples of lazy constraints I could find on Gurobi's website, and also in this StackExchange, the TSP is mentioned and the classic example is the sub-tour elimination constraints. However, for different kind of problems, how can I identify good "candidates" to be lazy constraints that can speed up the optimization? I guess the more a specific type of constraint appears is in the problem the better candidate it is. For instance, the sub-tour elimination constraints in the TSP are exponential, and that makes them very good candidates for being lazy constraints. Is there any other criterion to choose them?

And once I've identified them, assuming that I can enumerate all these constraints (which I can do for the problem that I am solving): is it better to use the callback approach or the enumeration one to add the lazy constraints?

cholo14
  • 233
  • 1
  • 5

1 Answers1

1

Good candidates for lazy constraints are constraints which are not active in the optimal solutions of the relaxations. Thus, removing them speeds up the relaxation.

For lazy constraints to be useful, there needs to be a significant difference in the sizes of the problem with all constraints and the problem without the lazy constraints.

If you can enumerate all the (lazy) constraints, adding them all seems better since the solver has more information. But I'm not sure that it makes a large difference in the end.

fontanf
  • 2,623
  • 6
  • 11
  • I concur with the last sentence. As far as I know, most (all?) good solvers use active set methods, where constraints that have been nonbinding for a while are put off to the side, reducing the dimension of the basis matrices. I'm not sure how that differs in general with lazy constraints, other than that (a) lazy constraints will not be present in the initial bases whereas the active set approach needs some iterations to identify constraints to set aside and (b) in a callback lazy constraints are typically constraints that were not known up front. – prubin Nov 16 '23 at 16:17