903. Enhancing the convergence of the Feasibility Pump through variable decomposition
Invited abstract in session MC-20: Metaheuristic algorithms, stream Combinatorial Optimization.
Monday, 12:30-14:00Room: Esther Simpson 2.11
Authors (first author is the speaker)
| 1. | Lucas Assuncao
|
| Université Le Havre Normandie | |
| 2. | Sebastian Urrutia
|
| University Molde | |
| 3. | Andréa Cynthia Santos
|
| Normandie, Normandie Université |
Abstract
Feasibility Pump (FP) is a well-known heuristic for mixed integer linear programming that iteratively moves fractional solutions toward integer feasibility by minimizing their distance to target integer points while maintaining the original linear constraints. Due to its simplicity and effectiveness, FP is widely used in commercial solvers, with many variations improving its convergence and solution quality. This work introduces a novel acceleration technique relying on the intuition that not all binary variables are active in a feasible solution. A kernel search strategy identifies a subset of promising binary variables, while the remaining ones are grouped into ranked buckets based on their likelihood of appearing in a feasible solution. FP sub-problems prioritize the kernel and gradually incorporate other variables as needed. To our knowledge, this is the first decomposition-based approach within the FP framework. Computational experiments on MIPLIB 2017 benchmark and two additional problems in vehicle routing and scheduling show improved success rates and reduced running times. Notably, the proposed method surpasses FP’s performance and finds feasible solutions in cases where CPLEX fails within an hour.
Keywords
- Programming, Mixed-Integer
- Combinatorial Optimization
- Algorithms
Status: accepted
Back to the list of papers