Reproduce “The Differentiable Feasibility Pump” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Matteo Cacciola, Alexandre Forel, Antonio Frangioni, Andrea Lodi
A Differentiable Feasibility Pump (DFP) framework was developed that reinterprets the classical Feasibility Pump (FP) as a gradient-descent algorithm. Applying a locally convex integrality loss or a novel differentiable feasibility loss for rounded solutions within DFP led to solving 7 more MILP instances and reducing the algorithm's restart ratio from 43.71% to 3.9% on MIPLIB benchmarks.
Key insights
- The original Feasibility Pump can be understood as a specific instance of a gradient-descent algorithm with a linear integrality loss and fixed parameters.
- Using a locally convex integrality loss (e.g., quadratic, p=2) significantly enhances algorithm stability and performance compared to the traditional linear loss, contradicting some prior interpretations.
- Directly penalizing the infeasibility of the rounded solution via a differentiable feasibility loss dramatically improves algorithmic stability, leading to a substantial reduction in heuristic restarts.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.