Sparsity of Lift-and-Project Cutting Planes
Sparsity of Lift-and-Project Cutting Planes
复制标题
提升和投影切割面的稀疏性
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Matthias Walter
中科院分区：
文献类型：
--
作者：
Matthias Walter
众所周知，稀疏性(即只有几个非零系数)是混合整数规划中割平面的理想性质。我们表明，在MIPLIB 2003问题实例集上，仅使用10个非常密集的割面(与模型中数千个约束相比)，导致LP求解器的运行时间平均增加25%。我们引入了对偶稀疏性(割的行乘数的一种性质)的概念，并证明了对偶稀疏性与原始(通常)稀疏性之间的强相关性。提升和项目削减关键取决于所谓的归一化的选择，我们比较了几个已知的归一化方法的实际稀疏性和可能的稀疏性。然后，测试一种新的规格化，该归一化改进了所生成的切割的对偶(因此是原始的)稀疏性。
It is well-known that sparsity (i.e. having only a few nonzero coefficients) is a desirable property for cutting planes in mixed-integer programming. We show that on the MIPLIB 2003 problem instance set, using only 10 very dense cutting planes (compared to thousands of constraints in a model), leads to a run time increase of 25 % on average for the LP-solver. We introduce the concept of dual sparsity (a property of the row-multipliers of the cut) and show a strong correlation between dual and primal (the usual) sparsity. Lift-and-project cuts crucially depend on the choice of a so-called normalization, of which we compared several known ones with respect to their actual and possible sparsity. Then a new normalization is tested that improves the dual (and hence the primal) sparsity of the generated cuts.