On the Size of Integer Programs with Bounded Coefficients or Sparse Constraints
On the Size of Integer Programs with Bounded Coefficients or Sparse Constraints
复制标题
关于有界系数或稀疏约束的整数规划的大小
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
M. Pfetsch
中科院分区：
文献类型：
--
作者：
Christopher Hojny;Hendrik Lüthen;M. Pfetsch
整数规划公式描述了一组整点上的优化问题。一个基本的问题是确定这些公式的最小大小，特别是如果系数的大小或约束的稀疏性是有界的。本文考虑了在原始空间和扩展空间中这些大小的上下限，即是否允许额外的变量。在原空间上，我们给出了系数有界整数公式大小的背包问题的下界。对于0/1-问题，我们还介绍了一种计算原空间中整数公式的非零点个数的紧下界的方法。此外，我们给出了关于这些界限的小维度的统计数据。最后，我们考虑了任意目标函数的整数优化问题可表示为混合整数规划的条件。特别地，我们证明了在某些特殊情况下，例如有效地确定或保持所有最优解，这些公式是不存在的。所有结果都用实例进行了说明。
Integer programming formulations describe optimization problems over a set of integer points. A fundamental problem is to determine the minimal size of such formulations, in particular, if the size of the coefficients or sparsity of the constraints is bounded. This article considers lower and upper bounds on these sizes both in the original and in extended spaces, i.e., if additional variables are allowed. We focus on the the original space, where we provide lower bounds for knapsack problems on the size of integer formulations with bounded coefficients. For 0/1-problems, we also introduce a technique to compute a tight lower bound on the number of non-zeros of integer formulations in the original space. Moreover, we present statistics on these bounds in small dimensions. Finally, we consider conditions on the representability of integer optimization problems with arbitrary objective function as mixed-integer programs. In particular, we show non-existence of such formulations in some special cases, e.g., efficient determination or preservation of all optimal solutions. All results are illustrated by examples.