A primal all-integer algorithm based on irreducible solutions
A primal all-integer algorithm based on irreducible solutions
复制标题
一种基于不可约解的原始全整数算法
DOI：
10.1007/s10107-003-0384-8
复制
发表时间：
2003
影响因子：
2.7
通讯作者：
R. Weismantel
中科院分区：
文献类型：
--
作者：
U. Haus;M. Köppe;R. Weismantel
本文介绍了一种求解一般线性整数规划的精确原始增广算法。该算法迭代地将Tableau中的一列替换为对应于某些线性丢番图不等式的不可约解的其他列。我们证明了我们算法的各种版本是有限的。如何有效地完成更换柱这一子问题，是本文主要关注的问题。最后给出了算法的具体实现。对MIPLIB的多个硬0/1整数规划的计算结果表明了该方法的实用性。
This paper introduces an exact primal augmentation algorithm for solving general linear integer programs. The algorithm iteratively substitutes one column in a tableau by other columns that correspond to irreducible solutions of certain linear diophantine inequalities. We prove that various versions of our algorithm are finite. It is a major concern in this paper to show how the subproblem of replacing a column can be accomplished effectively. An implementation of the presented algorithms is given. Computational results for a number of hard 0/1 integer programs from the MIPLIB demonstrate the practical power of the method.