Some polyhedra related to combinatorial problems
Some polyhedra related to combinatorial problems
复制标题
DOI：
10.1016/0024-3795(69)90017-2
复制
发表时间：
1969-10
影响因子：
1.1
通讯作者：
R. Gomory
中科院分区：
文献类型：
--
作者：
R. Gomory
本文首先描述了渐近整数规划的理论和算法。接下来介绍一类多面体。这些多面体的顶点提供了渐近整数规划问题的解决方案；它们的面是一般整数规划问题的剖切面，并且在某种程度上，多面体与满足线性规划问题的整数点的凸包重合。接下来显示这些多面体是更对称的高维多面体的横截面，然后研究其性质。概述了一些基于多面体知识的整数规划算法。
This paper first describes a theory and algorithms for asymptotic integer programs. Next, a class of polyhedra is introduced. The vertices of these polyhedra provide solutions to the asymptotic integer programming problem; their faces are cutting planes for the general integer programming problem and, to some extent, the polyhedra coincide with the convex hull of the integer points satisfying a linear programming problem. These polyhedra are next shown to be cross sections of more symmetric higher dimensional polyhedra whose properties are then studied. Some algorithms for integer programming, based on a knowledge of the polyhedra, are outlined.