The Gomory-Chvatal Closure of a Nonrational Polytope Is a Rational Polytope

被引：8

作者：

Dunkel, Juliane ^{[1
]}

Schulz, Andreas S. ^{[1
]}

机构：

[1] MIT, Ctr Operat Res, Cambridge, MA 02139 USA

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 2013年 / 38卷 / 01期

关键词：

Gomory-Chvatal closure; cutting planes; integer programming;

D O I：

10.1287/moor.1120.0565

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The question as to whether the Gomory-Chvatal closure of a nonrational polytope is a polytope has been a longstanding open problem in integer programming. In this paper, we answer this question in the affirmative by combining ideas from polyhedral theory and the geometry of numbers.

引用

页码：63 / 91

页数：29

共 11 条

[1]

Barvinok A, 2002, Graduate Studies in Mathematics, V54

[2]

Chvatal V., 1973, Discrete Mathematics, V4, P305, DOI 10.1016/0012-365X(73)90167-2

[3] Valid inequalities for mixed integer linear programs [J].

Cornuejols, Gerard .

MATHEMATICAL PROGRAMMING, 2008, 112 (01) :3-44

[4]

Dadush D, 2011, LECT NOTES COMPUT SC, V6655, P130, DOI 10.1007/978-3-642-20807-2_11

[5] The Chvatal-Gomory Closure of a Strictly Convex Body [J].

Dadush, Daniel ;

Dey, Santanu S. ;

Vielma, Juan Pablo .

MATHEMATICS OF OPERATIONS RESEARCH, 2011, 36 (02) :227-239

[6]

Dey SS, 2010, LECT NOTES COMPUT SC, V6080, P327, DOI 10.1007/978-3-642-13036-6_25

[7]

Gomory R., 1958, B AM MATH SOC, V64, P275, DOI [10.1090/S0002-9904-1958-10224-4, DOI 10.1090/S0002-9904-1958-10224-4]

[8] ARBITRARILY COMPLEX CORNER POLYHEDRA ARE DENSE IN RN [J].

HALFIN, S .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1972, 23 (02) :157-&

[9] FACTORING POLYNOMIALS WITH RATIONAL COEFFICIENTS [J].

LENSTRA, AK ;

LENSTRA, HW ;

LOVASZ, L .

MATHEMATISCHE ANNALEN, 1982, 261 (04) :515-534

[10]

Schrijver A., 1980, Annals of Discrete Mathematics, V9, P291

← 1 2 →