A recursive procedure to generate all cuts for 0–1 mixed integer programs
George L. Nemhauser1 and Laurence A. Wolsey2
| (1) | School of Industrial and Systems Engineering, Georgia Institute of Technology, 30332 Atlanta, GA, USA |
| (2) | Center for Operations Research and Econometrics, Université Catholique de Louvain, Louvain-la-Neuve, Belgium |
Received: 6 March 1985 Revised: 3 October 1988
Abstract We study several ways of obtaining valid inequalities for mixed integer programs. We show how inequalities obtained from a disjunctive argument can be represented by superadditive functions and we show how the superadditive inequalities relate to Gomory's mixed integer cuts. We also show how all valid inequalities for mixed 0–1 programs can be generated recursively from a simple subclass of the disjunctive inequalities.
Key words Cutting planes - valid inequalities - disjunctive inequalities - superadditive functions - 0–1 mixed integer programs
The research of this author was supported by NSF Contract No. ECS-8540898.
References secured to subscribers.