Fundamental Domains for Integer Programs with Symmetries
Fundamental Domains for Integer Programs with Symmetries
复制标题
具有对称性的整数规划的基本域
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
E. Friedman
中科院分区：
文献类型：
--
作者：
E. Friedman
定义了一个在群作用下对称的组合整数规划的线性规划松弛的基本域。然后，我们提供了一个构造的多面体的基本域定义的线性函数的最大化。这个基本域的计算在最坏的情况下是群大小的多项式。然而，对于对称群的特殊情况下，其大小是指数的整数规划的大小，我们展示了如何计算一个分离的超平面在多项式时间的整数规划的大小。
基本域可以提供一个简单的方法来减少计算困难，经常出现在整数规划的对称性。我们的构造与Kaibel和Pfetch的轨道位置的构造密切相关，但更简单，更一般，代价是创建新的非积分极值点。
We define a fundamental domain of a linear programming relaxation of a combinatorial integer program which is symmetric under a group action. We then provide a construction for the polytope of a fundamental domain defined by the maximization of a linear function. The computation of this fundamental domain is at worst polynomial in the size of the group. However, for the special case of the symmetric group, whose size is exponential in the size of the integer program, we show how to compute a separating hyperplane in polynomial time in the size of the integer program.
Fundamental domains may provide a straightforward way to reduce the computation difficulties that often arise in integer programs with symmetries. Our construction is closely related to the constructions of orbitopes by Kaibel and Pfetch, but are simpler and more general, at a cost of creating new non-integral extreme points.