Article ID: | iaor20041803 |
Country: | Germany |
Volume: | 96 |
Issue: | 2 |
Start Page Number: | 341 |
End Page Number: | 375 |
Publication Date: | Jan 2003 |
Journal: | Mathematical Programming |
Authors: | Johnson E.L., Gomory R.E. |
Keywords: | cutting plane algorithms |
In this paper we show how knowledge about T-space translates directly into cutting planes for general integer programming problems. After providing background on Corner Polyhedra and on T-space, this paper examines T-space in some detail. It gives a variety of constructions for T-space facets, all of which translate into cutting planes, and introduces continuous families of facets. In view of the great variety of possible facets, no one of which can be dominated either by any other or by any combination of the others, a measure of merit is introduced to provide guidance on their usefulness. T-spaces based on higher dimensional groups are discussed briefly as is the idea of going beyond cutting planes to iterated approximations of Corner Polyhedra.