Tightening constraints for better formulation

Question

Lately, I have been reading a lot of papers where the constraints have been tightened to include better formulations leading to decrease in optimiality gaps and also the time for solving the optimisation problem. I was wondering if there is a book or paper which folks would be aware about introducing constraint tightening in MIPs? I don't imagine it to be hit and trial approach, there definitely seems to be some good theory behind it.

Answer 1

The cutting plan algorithm is really a strange method to solve integer programming. In some cases, it works very well, and in some cases, it works vice versa. I think besides the theoretical overview of this method many trials and errors should be applied to understand how it works well on a specific problem. In this case, some resources that might be useful are:

• Integer Programming: Laurence Wolsey
• Algorithm for simplifying a set of linear inequalities
• Valid Inequalities and Strong Inequalities
• Valid Inequality Verification for MIP
• Converting Weak to Strong MIP Formulations (Gurobi webinar)
• Performance of a branch and bound algorithm VS branch-cut-heuristics
• Learning to Select Cuts for Efficient Mixed-Integer Programming
• Tobias Achtenberg PhD thesis
• Cutting Plane Separators in SCIP