A strongly polynomial algorithm for bimodular integer linear programming
A strongly polynomial algorithm for bimodular integer linear programming
复制标题
双模整数线性规划的强多项式算法
DOI：
10.1145/3055399.3055473
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
R. Zenklusen
中科院分区：
文献类型：
--
作者：
S. Artmann;R. Weismantel;R. Zenklusen
本文给出了求解max{cTx：Ax≤ B，xε n }型整数规划的一个强多项式算法，其中Aε ∈ mXn，秩（A）=n，Bε≤m，cε≤n，且A的（nXn）-子矩阵的所有行列式的绝对值有界为2.特别地，这意味着整数规划max{cTx：Q x≤ B，xε n ≥ 0 n}，其中Qε n mXn具有所有子行列式绝对值有界于2的性质，可以在强多项式时间内求解.因此，我们得到了一个著名的结果，整数规划的约束矩阵是完全么模的强多项式时间可解。
We present a strongly polynomial algorithm to solve integer programs of the form max{cT x: Ax≤ b, xεℤn }, for AεℤmXn with rank(A)=n, bε≤m, cε≤n, and where all determinants of (nXn)-sub-matrices of A are bounded by 2 in absolute value. In particular, this implies that integer programs max{cT x : Q x≤ b, xεℤ≥0n}, where Qε ℤmXn has the property that all subdeterminants are bounded by 2 in absolute value, can be solved in strongly polynomial time. We thus obtain an extension of the well-known result that integer programs with constraint matrices that are totally unimodular are solvable in strongly polynomial time.