Integral Simplex Using Decomposition for the Set Partitioning Problem
Integral Simplex Using Decomposition for the Set Partitioning Problem
复制标题
使用分解解决集合划分问题的积分单纯形
DOI：
--
复制
发表时间：
2013
影响因子：
2.7
通讯作者：
Issmail Elhallaoui
中科院分区：
文献类型：
--
作者：
Abdelouahab Zaghrouti;F. Soumis;Issmail Elhallaoui
自20世纪70年代以来，一些作者研究了集划分多面体的结构，并提出了通过基本整数解序列找到最优解的单纯形算法的适应性。Balas和Padberg在1972年证明了这样一个序列的存在性，并且代价不增加，但是简并使得很难找到序列的项。本文利用改进的原始单纯形的思想，有效地处理退化和寻找序列中的后续项。当不存在导致更好的整数解的输入变量时，被称为积分单纯形的算法使用分解算法使用子问题来找到一组变量以输入到基中以获得这样的解。我们改进的Balas和Padberg的结果，通过引入一个建设性的方法，发现这个序列只使用正常的枢轴上的正系数。我们目前的结果与多达500，000个变量的最佳整数解往往是没有任何分支获得的大规模问题。
Since the 1970s, several authors have studied the structure of the set partitioning polytope and proposed adaptations of the simplex algorithm that find an optimal solution via a sequence of basic integer solutions. Balas and Padberg in 1972 proved the existence of such a sequence with nonincreasing costs, but degeneracy makes it difficult to find the terms of the sequence. This paper uses ideas from the improved primal simplex to deal efficiently with degeneracy and find subsequent terms in the sequence. When there is no entering variable that leads to a better integer solution, the algorithm referred to as the integral simplex using decomposition algorithm uses a subproblem to find a group of variables to enter into the basis in order to obtain such a solution. We improve the Balas and Padberg results by introducing a constructive method that finds this sequence by only using normal pivots on positive coefficients. We present results for large-scale problems with up to 500,000 variables for which optimal integer solutions are often obtained without any branching.