Optimization Online


On the generation of cutting planes which maximize the bound improvement

Stefano Coniglio (stefano.coniglio***at***gmail.com)
Martin Tieves (tieves***at***math2.rwth-aachen.de)

Abstract: 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.

Keywords: Integer Programming, Cutting Panes

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 10/24/2013
Entry Accepted: 10/24/2013
Entry Last Modified: 09/23/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society