我们考虑求解形式为min{cτx: Ax = b, x∈Z≥0}的整数规划问题，其中A是一个多级随机矩阵，其意义如下:A的原始树深度被一个参数d所限制，这意味着A的列可以被组织成深度最多为d的根森林，这样不受祖先/后代关系约束的列在同一行中就不会有非零项。我们给出一个算法,解决了这一问题在固定参数f (d,∥∥∞)·nlogO (2 d) n、f是一个可计算函数和n的行数的强大的算法模型,运行时间只有措施单位算术运算的输入数字和不依赖他们的bitlength。这是第一个多阶段随机整数规划的fpt算法，在强意义上几乎达到线性运行时间。两阶段随机整数项目,我们的算法在时间2 ((r + s)∥∥∞)O (r (r + s))·nlogO (rs) n,既改善了以前的方法的多项式因子和r和s的依赖。事实上,r = 1依赖年代是渐近紧假设指数时间的假设。我们的算法也可以并行化:我们在PRAM模型中给出了一个实现，使用n个处理器实现运行时间f(d，∥A∥∞)·logO(2d) n。我们算法的主要概念是对多阶段随机整数规划的一个新的近似结果。我们证明,如果我们考虑一个整数程序P,说与约束矩阵,然后对每一个最优解的线性松弛P存在一个最佳(积分)解决P,谎言,在ℓ∞范数,在距离由一个函数有界的∥∥∞的原始treedepth a达到这个结果的路上,证明了Klein关于多阶段随机整数规划的一个结构结果的推广和相当的改进。一旦接近的结果建立起来，这就允许我们应用基于树深的分支策略，该策略由线性松弛的最佳解决方案指导。

Let A ∈ Zm×n be an integral matrix and a, b, c ∈ Z satisfy a ≥ b ≥ c ≥ 0. The question is to recognize whether A is {a, b, c}-modular, i.e., whether the set of n×n subdeterminants of A in absolute value is {a, b, c}. We will succeed in solving this problem in polynomial time unless A possesses a duplicative relation, that is, A has nonzero n × n subdeterminants k1 and k2 satisfying 2·|k1|=|k2|. This is an extension of the well-known recognition algorithm for totally unimodular matrices. As a consequence of our analysis, we present a polynomial time algorithm to solve integer programs in standard form over {a, b, c}-modular constraint matrices for any constants a, b and c.

我们介绍整数程序（IP）的完整性编号。粗略地说，完整性数是通过混合整数(MIP)松弛来求解IP所需的最小整数约束数。这个数的一个显著性质是它在约束矩阵的幺模变换下的不变性。考虑到约束矩阵的最大次数，我们的分析允许我们制作以下形式的陈述：存在一个数字（三角洲），使得具有n个变量的IP和n +根n / tau（delta）许多不等式可以通过少于N整数约束的MIP松弛来解决约束。从我们的结果，它遵循仅由N个约束定义的IP可以通过MIP松弛与O（根Delta）进行许多整数约束来解决。

在子集选择中，我们搜索涉及小的变量子集的最佳线性预测器。从计算复杂性观点来看，子集选择是NP - 硬，并且已知很少的类是在多项式时间中可溶的。主要使用来自离散几何的工具，我们表明原始数据矩阵上的一些稀疏条件允许我们解决多项式时间中的问题。

我们考虑整数计划（IP）稀疏功能的渐近分布，测量最佳IP解决方案的最小支持，以及IP到线性程序（LP）距离功能，这测量了最佳IP和LP解决方案之间的距离。我们为研究与整数优化相关的一般函数的渐近分布来创建一个框架。已经有大量的研究集中在这些功能可以获得的极端值上。然而，较少是众所周知的典型值。这些功能中的每一个被定义用于固定约束矩阵和目标向量，而右侧侧面被视为输入。我们表明这些功能的典型值小于所知道的最坏情况界限，通过提供控制其整体渐近分布的概率样结果。©2020工业和应用数学协会。

我们引入不等式形式的整数规划的完整性数。粗略地说，完整性数是通过混合整数(MIP)松弛来求解IP所需的最小整数约束数。这个数的一个显著性质是它在约束矩阵的幺模变换下的不变性。考虑最大的小Δ约束矩阵,我们的分析使我们能够做出的声明以下形式:存在数字τ(Δ)和κ(Δ)这样一个IP与n≥τ(Δ)许多变量和n +κ(Δ)⋅n−−√许多不等式约束可以解决通过MIP少于n个整数约束的放松。我们结果的一个特殊实例表明，只有n个约束定义的ip可以通过具有O(Δ−−√)多个整数约束的MIP松弛来求解。