On chvátal's cutting planes in integer linear programming
作者:
I.G. Rosenberg,
期刊:
Mathematische Operationsforschung und Statistik
(Taylor Available online 1975)
卷期:
Volume 6,
issue 4
页码: 511-522
ISSN:0047-6277
年代: 1975
DOI:10.1080/02331887508801232
出版商: Akademie-Verlag
数据来源: Taylor
摘要:
A new class of cutting planes (for integar linear programs) recently introduced by V. Chvátal is discussed. It is shown that Gomary's fundamental cuts are special cases of these cuts. A formula for the depth of a cut with respect to the cone is found. For cuts formed from from binding inequalities only, the optimal choice is reduced to a system of non-linear integar programs. It is shown that under special circumstances Chvátal's cuts formed from all inequalities can be replaced by cuts formed from binding inequalities without decreasing the depth. The above results re applied to fundamental cuts.
点击下载:
PDF (584KB)
返 回