Speaker
Stefano Coniglio, University of Bergamo
Abstract
We introduce the notion of a bound-optimal cut: a cut that yields the largest possible bound improvement when added to the relaxation of a Mixed Integer Linear Optimization Problem (MILP). For cuts with a MILP separation problem, we show how to generate a bound-optimal cut by solving a Quadratically Constrained Quadratic Optimization Problem and how to recast it as an MILP for cuts with binary left-hand side coefficients and an affinely-dependant right-hand side. We study several properties of this problem, including how to extend it to generate k cuts with together yield the largest bound improvement. We assess the impact of bound-optimal cuts for the generation of stable set inequalities for the max clique problem; knapsack constraints for the dual of the fractional bin-packing problem; and; and split cuts for the max clique problem. Our results show that, when compared to separating maximally violated cuts, bound-optimal cuts lead to the target bound in a much smaller number of iterations.