论文标题
推送：基于可行性泵和移动的原始启发式
PUSH: a primal heuristic based on Feasibility PUmp and SHifting
论文作者
论文摘要
这项工作描述了Push，这是一种原始的启发式，结合了可行性泵和移动。主要思想是通过适当的转移和其他圆形启发式方法来代替可行性泵的圆形阶段。该算法提出了不同的策略，具体取决于获得的部分舍入的性质。特别是，我们区分了何时可行的部分解决方案，与潜在的候选者不可行，而没有候选者是不可行的。我们使用阈值指示使用算法将变量的百分比，而其他变量则可以圆形到最近的整数。最重要的是，我们的算法直接处理平等约束而无需复制行。我们在2022年MIP竞赛的19个实例上选择了算法的参数。最后，我们将我们的方法与其他开始启发式方法进行了比较，例如第一个800 MIPLIB2017实例中的简单圆形，圆形，舍入，移动和可行性泵，该实例按非零件数量订购。
This work describes PUSH, a primal heuristic combining Feasibility Pump and Shifting. The main idea is to replace the rounding phase of the Feasibility Pump with a suitable adaptation of the Shifting and other rounding heuristics. The algorithm presents different strategies, depending on the nature of the partial rounding obtained. In particular, we distinguish when the partial solution is feasible, infeasible with potential candidates, and infeasible without candidates. We used a threshold to indicate the percentage of variables to round with our algorithm and which other to round to the nearest integer. Most importantly, our algorithm tackles directly equality constraints without duplicating rows. We select the parameters of our algorithm on the 19 instances provided for the Mip Competition 2022. Finally, we compared our approach to other start heuristics, like Simple Rounding, Rounding, Shifting, and Feasibility Pump on the first 800 MIPLIB2017 instances ordered by the number of non-zeros.
