Cutting Planes in Integer and Mixed Integer Programming
Please always quote using this URN: urn:nbn:de:0297-zib-4339
- This survey presents cutting planes that are useful or potentially useful in solving mixed integer programs. Valid inequalities for i) general integer programs, ii) problems with local structure such as knapsack constraints, and iii) problems with 0-1 coefficient matrices, such as set packing, are examined in turn. Finally the use of valid inequalities for classes of problems with structure, such as network design, is explored.
Author: | Hugues Marchand, Alexander Martin, Robert Weismantel, Laurence Wolsey |
---|---|
Document Type: | ZIB-Report |
Tag: | Cutting Planes; Mixed Integer Programming |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming | |
Date of first Publication: | 1999/12/16 |
Series (Serial Number): | ZIB-Report (SC-99-44) |
ZIB-Reportnumber: | SC-99-44 |
Published in: | Paper available at URL http://www.core.ucl.ac.be/services/psfiles/dp99/dp9953.pdf Technical Report CORE DP9953, Universite Catholique de Louvain, Louvain-la-Neuve, Belgium, 1999 |