A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity
A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity
复制标题
ILP 内核的结构方法：树宽和总单模性
DOI：
10.1007/978-3-662-48350-3_65
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Stefan Kratsch
中科院分区：
文献类型：
--
作者：
Bart M. P. Jansen;Stefan Kratsch
核化是NP难问题有效预处理的理论形式化。从经验上讲，预处理在实践中非常成功，例如在最先进的ILP求解器中，如CPLEX。受此启发，以前的工作研究了ILP相关问题的核化的存在，例如，以检验Ax ≤B的可行性。然而，与观察到的CPLEX的成功相比，结果基本上是负面的。直观地说，实际的例子有更有用的结构比最坏的情况下，用于证明这些bounds.In本文中，我们研究的效果，子系统有（一个Gaifman图）有界树宽或完全么模的ILP可行性问题的核化。我们表明，在积极的一面，如果这些子系统有一个小的变量，他们与其余的实例相互作用，那么我们可以有效地将它们替换为较小的子系统的大小多项式域中，而不改变可行性。因此，如果一个实例的大部分由这样的子系统组成，那么这会产生相当大的尺寸缩减。补充这一点，我们证明，松弛所考虑的结构，例如，子系统的较大边界允许最坏情况下的内核化下限。因此，这些宽松的结构产生的实例族不能有效地减少，通过任何方法。
Kernelization is a theoretical formalization of efficient preprocessing forNP-hard problems. Empirically, preprocessing is highly successful in practice, for example in state-of-the-art ILP-solvers like CPLEX. Motivated by this, previous work studied the existence of kernelizations for ILP related problems, e.g., for testing feasibility ofAx≤b. In contrast to the observed success of CPLEX, however, the results were largely negative. Intuitively, practical instances have far more useful structure than the worst-case instances used to prove these lower bounds.In the present paper, we study the effect that subsystems that have (a Gaifman graph of) bounded treewidth or that are totally unimodular have on the kernelizability of the ILP feasibility problem. We show that, on the positive side, if these subsystems have a small number of variables on which they interact with the remaining instance, then we can efficiently replace them by smaller subsystems of size polynomial in the domain without changing feasibility. Thus, if large parts of an instance consist of such subsystems, then this yields a substantial size reduction. Complementing this we prove that relaxations to the considered structures, e.g., larger boundaries of the subsystems, allow worst-case lower bounds against kernelization. Thus, these relaxed structures give rise to instance families that cannot be efficiently reduced, by any approach.
整数线性规划的多项式核：覆盖、打包和可行性
DOI：
10.1007/978-3-642-40450-4_55
发表时间：
2013
期刊：
影响因子：
--
作者：
Stefan Kratsch
通讯作者：
Stefan Kratsch
稀疏整数线性规划的多项式核
DOI：
--
发表时间：
2013
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
Stefan Kratsch
通讯作者：
Stefan Kratsch
DOI：
10.1145/2797140
发表时间：
2012-07
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
Eun Jung Kim;Alexander Langer;C. Paul;F. Reidl;P. Rossmanith;Ignasi Sau;S. Sikdar
通讯作者：
Eun Jung Kim;Alexander Langer;C. Paul;F. Reidl;P. Rossmanith;Ignasi Sau;S. Sikdar