论文标题
有效计算松弛复杂性的MIP技术
Efficient MIP Techniques for Computing the Relaxation Complexity
论文作者
论文摘要
多面体中包含的整数点X集的松弛复杂性RC（X）是在不使用辅助变量的情况下在X上制定线性优化问题所需的最小数量。除了其在整数编程中的相关性外，该概念在社会选择，对称的隐式分析和机器学习方面都具有解释。 我们采用有效的混合构成编程技术来计算放松复杂性的鲁棒和数值更实用的变体。我们提出的模型需要行或列的生成技术，可以通过对称处理和合适的传播算法来增强。从理论上讲，我们根据模型的LP松弛值比较了模型的质量。这些模型的性能在广泛的测试集上进行了研究，并以它们解决以前无法解决的具有挑战性实例的能力强调。
The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the minimal number of inequalities needed to formulate a linear optimization problem over X without using auxiliary variables. Besides its relevance in integer programming, this concept has interpretations in aspects of social choice, symmetric cryptanalysis, and machine learning. We employ efficient mixed-integer programming techniques to compute a robust and numerically more practical variant of the relaxation complexity. Our proposed models require row or column generation techniques and can be enhanced by symmetry handling and suitable propagation algorithms. Theoretically, we compare the quality of our models in terms of their LP relaxation values. The performance of those models is investigated on a broad test set and is underlined by their ability to solve challenging instances that could not be solved previously.
