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.
翻译:数十年来,整数线性编程的主要技术一直是分流和剪切。最近,一些作者开发了解决对称整数线性程序的核心点方法。如果其轨道多极点是无线性的,则将整数点称为核心点。已经证明,对于对称性ILP,优化于一组核心点的答案与考虑整个空间的答案相同。现有的核心点技术取决于核心点数(或等值类)是有限的,这需要特殊的对称组。在本文件中,我们开发了一些解决对称的 ILP(基于核心点的外部近似值)的新方法,这些方法并不取决于有限性,而如果该组组在生成器中存在很大的脱节周期,则效率更高。