Strengthening Chvátal-Gomory cuts and Gomory fractional cuts

作者: Adam N. Letchford , Andrea Lodi

DOI: 10.1016/S0167-6377(02)00112-8

关键词:

摘要: Chvátal–Gomory and Gomory fractional cuts are well-known cutting planes for pure integer programming problems. Various methods for strengthening them are known, for example based on subadditive functions or disjunctive techniques. We present a new and surprisingly simple strengthening procedure, discuss its properties, and present some computational results.

参考文章(17)
Claude-Alain Burdet, Ellis L. Johnson, A Subadditive Approach to Solve Linear Integer Programs Studies in Integer Programming. ,vol. 1, pp. 117- 143 ,(1977) , 10.1016/S0167-5060(08)70730-1
Ralph E. Gomory, Ellis L. Johnson, Some continuous functions related to corner polyhedra Mathematical Programming. ,vol. 3-3, pp. 23- 85 ,(1972) , 10.1007/BF01584976
Laurence A. Wolsey, George L. Nemhauser, Integer and Combinatorial Optimization ,(1988)
Egon Balas, Sebastián Ceria, Gérard Cornuéjols, A lift-and-project cutting plane algorithm for mixed 0-1 programs Mathematical Programming. ,vol. 58, pp. 295- 324 ,(1993) , 10.1007/BF01581273
Silvano Martello, Francesco Maffioli, Mauro Dell'Amico, Annotated Bibliographies in Combinatorial Optimization ,(1997)
Gérard Cornuéjols, Yanjun Li, Elementary closures for integer programs Operations Research Letters. ,vol. 28, pp. 1- 8 ,(2001) , 10.1016/S0167-6377(00)00067-5
Ralph E. Gomory, Outline of an algorithm for integer solutions to linear programs Bulletin of the American Mathematical Society. ,vol. 64, pp. 275- 278 ,(1958) , 10.1090/S0002-9904-1958-10224-4
Friedrich Eisenbrand, On the Membership Problem for the Elementary Closure of a Polyhedron Combinatorica. ,vol. 19, pp. 297- 300 ,(1999) , 10.1007/S004930050057
Egon Balas, Robert G. Jeroslow, Strengthening cuts for mixed integer programs European Journal of Operational Research. ,vol. 4, pp. 224- 234 ,(1980) , 10.1016/0377-2217(80)90106-X
Mark Hartmann, Maurice Queyranne, Yaoguang Wang, On the Chvátal Rank of Certain Inequalities integer programming and combinatorial optimization. pp. 218- 233 ,(1999) , 10.1007/3-540-48777-8_17