We propose the bound-optimal cutting plane method. It is a new paradigm for cutting plane generation in Mixed Integer Programming allowing for the simultaneous generation of k cuts which, when added to the current Linear Programming elaxation, yield the largest bound improvement. By Linear Programming duality arguments and standard linearization techniques we show that, for a large family of cutting planes, the cut generating problem of our cutting plane method can be formulated as a Mixed 0-1 Integer Program. We highlight the potential of our technique by presenting computational experiments on the generation of bound-optimal stable set inequalities for the fractional clique number problem. We compare our method to the standard generation of maximally violated cuts, to the generation of cutting planes corresponding to a steepest-edge pivot in the dual, and to coordinated cutting plane generation. With respect to the standard algorithm, the bound-optimal cutting plane method allows for a substantial reduction in the number of cutting plane iterations and/or cuts needed to achieve either a given bound or an optimal solution. This reduction is still substantial also in comparison to the other techniques.
Article
View On the generation of cutting planes which maximize the bound improvement