Parameterized Algorithms for MILPs with Small Treedepth
Parameterized Algorithms for MILPs with Small Treedepth
复制标题
DOI：
10.1609/aaai.v35i14.17454
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Cornelius Brand;Martin Kouteck'y;S. Ordyniak
中科院分区：
文献类型：
--
作者：
Cornelius Brand;Martin Kouteck'y;S. Ordyniak
求解（混合）整数（线性）规划，简称（M）I（L）Ps，是一项基本的优化任务，在人工智能和计算机科学中有广泛的应用。虽然一般来说很难，但近年来已经取得了巨大的进展，解决结构限制，（非混合）ILP：n倍，树倍，2阶段随机和多阶段随机程序承认有效的算法，所有这些特殊情况都包含在一类ILP的小树深。在本文中，我们将这条线的工作的混合情况下，通过显示一个算法求解MILP在时间f（a，d）poly（n），其中a是最大的系数的约束矩阵，d是它的树深，n是变量的数量。这是通过证明有界树深（非整数）线性规划的顶点的分解子（分数）的界来实现的。我们这样做，通过仔细分析可逆子矩阵的约束矩阵的逆。这使我们能够将混合程序扩展到整数网格，并将已知的方法应用于整数程序。然后，我们跟踪我们的“有界分形”的方法的限制边界，无论是在超越MILP（通过允许非线性目标），以及它的有用性概括其他重要的已知易处理类的ILP。在积极的一面，我们表明，我们的结果可以推广到MIP与分段线性可分凸目标整数断点。在消极的一面，我们表明，甚至稍微超出这些目标或考虑其他自然相关的易处理类的ILP导致无界分形。最后，我们表明，限制结构的约束矩阵中的积分变量不产生易处理的特殊情况。
Solving (mixed) integer (linear) programs, (M)I(L)Ps for short, is a fundamental optimisation task with a wide range of applications in artificial intelligence and computer science in general. While hard in general, recent years have brought about vast progress for solving structurally restricted, (non-mixed) ILPs: n-fold, tree-fold, 2-stage stochastic and multi-stage stochastic programs admit efficient algorithms, and all of these special cases are subsumed by the class of ILPs of small treedepth. In this paper, we extend this line of work to the mixed case, by showing an algorithm solving MILP in time f(a,d)poly(n), where a is the largest coefficient of the constraint matrix, d is its treedepth, and n is the number of variables. This is enabled by proving bounds on the denominators (fractionality) of the vertices of bounded-treedepth (non-integer) linear programs. We do so by carefully analysing the inverses of invertible sub-matrices of the constraint matrix. This allows us to afford scaling up the mixed program to the integer grid, and applying the known methods for integer programs. We then trace the limiting boundary of our "bounded fractionality" approach both in terms of going beyond MILP (by allowing non-linear objectives) as well as its usefulness for generalising other important known tractable classes of ILP. On the positive side, we show that our result can be generalised from MILP to MIP with piece-wise linear separable convex objectives with integer breakpoints. On the negative side, we show that going even slightly beyond such objectives or considering other natural related tractable classes of ILP leads to unbounded fractionality. Finally, we show that restricting the structure of only the integral variables in the constraint matrix does not yield tractable special cases.