论文标题
整数编程的核心点的外近似值
Outer approximations of core points for integer programming
论文作者
论文摘要
几十年来，整数线性编程的主要技术一直是分支和切割平面。最近，几位作者开发了解决对称整数线性程序（ILP）的核心点方法。如果其轨道多层不晶格，则将整数点称为核心点。已经表明，对于对称ILP，优化在一组核心点上给出了与考虑整个空间相同的答案。现有的核心点技术依赖于有限的核心点（或等效类）的数量，这需要特殊的对称组。在本文中，我们开发了一些新的方法来求解不依赖于有限的对称ILP（基于核心点的外近似值），但如果该组在其一组发生器中具有较大的脱节周期，则更有效。
For several decades the dominant techniques for integer linear programming have been branching and cutting planes. Recently, several authors have developed core point methods for solving symmetric integer linear programs (ILPs). An integer point is called a core point if its orbit polytope is lattice-free. It has been shown that for symmetric ILPs, optimizing over the set of core points gives the same answer as considering the entire space. Existing core point techniques rely on the number of core points (or equivalence classes) being finite, which requires special symmetry groups. In this paper we develop some new methods for solving symmetric ILPs (based on outer approximations of core points) that do not depend on finiteness but are more efficient if the group has large disjoint cycles in its set of generators.
