论文标题
如何在多面体中找到所有整数点的凸壳？
How to Find the Convex Hull of All Integer Points in a Polyhedron?
论文作者
论文摘要
我们提出了一种基于剪切的算法，用于查找由线性不等式系统定义的多面体的所有整数点的所有顶点和所有方面。我们的算法DDM剪切基于Gomory剪切和双重描述方法的动态版本。我们描述了算法的计算机实现，并提出了将我们的算法与幼稚算法进行比较的计算实验结果。
We propose a cut-based algorithm for finding all vertices and all facets of the convex hull of all integer points of a polyhedron defined by a system of linear inequalities. Our algorithm DDM Cuts is based on the Gomory cuts and the dynamic version of the double description method. We describe the computer implementation of the algorithm and present the results of computational experiments comparing our algorithm with a naive one.
