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.
翻译:这项工作描述PUSH, 将可行性泵和变换结合起来, 主要是用调整和其他四舍五入法的适当调整取代可行性泵的圆形阶段。 算法根据部分四舍五入的性质, 提出了不同的策略。 特别是, 我们区分部分解决方案何时可行, 与潜在候选人不可行, 并且没有候选人也不可能。 我们用一个阈值来表示变量与我们的算法相圆的百分比, 以及其它变量与最近的整数相圆的百分比。 最重要的是, 我们的算法直接解决平等限制, 而不重复行。 我们从为Mip 比赛 2022 提供的19个实例中选择了我们的算法参数。 最后, 我们比较了我们的方法与其他开始的超标准, 比如简单四舍五入法、 圆法、 变换法和 可行性泵, 最初800 MIPLIB2017 例, 由非零数所订购。