Obtaining clique, cover and coefficient reduction inequalities as Chvatal-Gomory inequalities and Gomory fractional cuts
作者： B.L. Dietrich , L.F. Escudero
DOI: 10.1016/0377-2217(94)90250-X
关键词:
摘要: Abstract We show how clique and cover induced inequalities implied from 0–1 knapsack constraints can be obtained as Chvatal-Gomory inequalities. LP tighter equivalent to by the ‘big M’ reduction procedure also generated some extended coefficient based Gomory fractional cuts.
elsevier.com
sci-hub.se 参考文章(7)
B.L. Dietrich, L.F. Escudero, F. Chance, Efficient reformulation for 0-1 programs: methods and computational results Discrete Applied Mathematics. ,vol. 42, pp. 147- 175 ,(1993) , 10.1016/0166-218X(93)90044-O
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
Monique Guignard, Kurt Spielberg, Logical Reduction Methods in Zero-One Programming—Minimal Preferred Variables Operations Research. ,vol. 29, pp. 49- 74 ,(1981) , 10.1287/OPRE.29.1.49
Tony J. Van Roy, Laurence A. Wolsey, Solving Mixed Integer Programming Problems Using Automatic Reformulation Operations Research. ,vol. 35, pp. 45- 57 ,(1987) , 10.1287/OPRE.35.1.45
Ellis L. Johnson, Michael M. Kostreva, Uwe H. Suhl, Solving 0-1 Integer Programming Problems Arising from Large Scale Planning Models Operations Research. ,vol. 33, pp. 803- 819 ,(1985) , 10.1287/OPRE.33.4.803
V. Chvátal, Edmonds polytopes and a hierarchy of combinatorial problems Discrete Mathematics. ,vol. 306, pp. 305- 337 ,(1973) , 10.1016/0012-365X(73)90167-2
Harlan Crowder, Ellis L. Johnson, Manfred Padberg, Solving Large-Scale Zero-One Linear Programming Problems Operations Research. ,vol. 31, pp. 803- 834 ,(1983) , 10.1287/OPRE.31.5.803