将可行性泵重构成可微优化，提升求解效率
The Differentiable Feasibility Pump
- 把传统可行性泵看作特定参数的梯度下降算法
- 改进梯度更新和损失函数，减少求解迭代次数
- 适合想加速混合整数规划求解的研究者
尽管可行性泵算法问世已近20年，仍是求解混合整数线性规划可行解的常用启发式方法。其核心包含两个步骤：求解原问题的线性松弛以获得满足约束的解，再通过舍入得到整数解。本文揭示，传统可行性泵及其多数扩展均可视为具有特定参数的梯度下降算法。关键在于观察到该算法对线性松弛解关于其目标函数的可微性。这一重理解为改进原始算法提供了新途径。我们研究了如何调整梯度更新步骤及扩展损失函数，并在MIPLIB实例上进行了大量实验，结果表明这些改进能显著减少找到可行解所需的迭代次数。
原文摘要 · Abstract (English)
Although nearly 20 years have passed since its conception, the feasibility pump algorithm remains a widely used heuristic to find feasible primal solutions to mixed-integer linear problems. Many extensions of the initial algorithm have been proposed. Yet, its core algorithm remains centered around two key steps: solving the linear relaxation of the original problem to obtain a solution that respects the constraints, and rounding it to obtain an integer solution. This paper shows that the traditional feasibility pump and many of its follow-ups can be seen as gradient-descent algorithms with specific parameters. A central aspect of this reinterpretation is observing that the traditional algorithm differentiates the solution of the linear relaxation with respect to its cost. This reinterpretation opens many opportunities for improving the performance of the original algorithm. We study how to modify the gradient-update step as well as extending its loss function. We perform extensive experiments on MIPLIB instances and show that these modifications can substantially reduce the number of iterations needed to find a solution.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。