An Algorithmic Theory of Integer Programming
An Algorithmic Theory of Integer Programming
复制标题
整数规划的算法理论
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
S. Onn
中科院分区：
文献类型：
--
作者：
F. Eisenbrand;Christoph Hunkenschröder;Kim;Martin Koutecký;Asaf Levin;S. Onn
我们研究了一般整数规划问题，其中变量数$n$是输入的一个可变部分。我们考虑约束矩阵$A$的两个自然参数：它的数值测度$A$和它的稀疏测度$d$。我们证明了整数规划可以在时间$g(a,d) extrm{poly}(n，L)$中求解，其中$g$是参数$a$和$d$的可计算函数，$L$是输入的二进制编码长度。特别地，整数规划是由$a$和$d$参数化的固定参数可处理的，并且对于每个固定$a$和$d$在多项式时间内可解。我们的结果也推广到非线性可分离凸目标函数。此外，对于线性目标，我们推导了一个强多项式算法，即运行时间$g(a,d) extrm{poly}(n)$，独立于输入数据的其余部分。
We study the general integer programming problem where the number of variables $n$ is a variable part of the input. We consider two natural parameters of the constraint matrix $A$: its numeric measure $a$ and its sparsity measure $d$. We show that integer programming can be solved in time $g(a,d) extrm{poly}(n,L)$, where $g$ is some computable function of the parameters $a$ and $d$, and $L$ is the binary encoding length of the input. In particular, integer programming is fixed-parameter tractable parameterized by $a$ and $d$, and is solvable in polynomial time for every fixed $a$ and $d$. Our results also extend to nonlinear separable convex objective functions. Moreover, for linear objectives, we derive a strongly-polynomial algorithm, that is, with running time $g(a,d) extrm{poly}(n)$, independent of the rest of the input data.
We obtain these results by developing an algorithmic framework based on the idea of iterative augmentation: starting from an initial feasible solution, we show how to quickly find augmenting steps which rapidly converge to an optimum. A central notion in this framework is the Graver basis of the matrix $A$, which constitutes a set of fundamental augmenting steps. The iterative augmentation idea is then enhanced via the use of other techniques such as new and improved bounds on the Graver basis, rapid solution of integer programs with bounded variables, proximity theorems and a new proximity-scaling algorithm, the notion of a reduced objective function, and others.
As a consequence of our work, we advance the state of the art of solving block-structured integer programs. In particular, we develop near-linear time algorithms for $n$-fold, tree-fold, and $2$-stage stochastic integer programs. We also discuss some of the many applications of these classes.
一种更快的树深度参数化算法
DOI：
10.1007/978-3-662-43948-7_77
发表时间：
2014
期刊：
影响因子：
--
作者：
Felix Reidl;Peter Rossmanith;Fernando Sánchez Villaamil;Somnath Sikdar
通讯作者：
Somnath Sikdar
ILP 内核的结构方法：树宽和总单模性
DOI：
10.1007/978-3-662-48350-3_65
发表时间：
2015
期刊：
影响因子：
--
作者：
Bart M. P. Jansen;Stefan Kratsch
通讯作者：
Stefan Kratsch