.png){kind=icon}
.png){kind=icon}
Return
Local-MIP: Efficient Local Search for Mixed Integer Programming
.png){kind=icon}
PRE
AI
DOI：10.1016/j.artint.2025.104405.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Mixed Integer Programming (MIP) is a fundamental model in operations research with broad industrial applications. Local search is a powerful method for addressing complex optimization problems; however, the development of local search algorithms for MIP still needs exploration. In this work, we introduce Local-MIP, an efficient local search algorithm tailored for MIP that integrates novel operators and employs a two-mode architecture to adaptively apply operators based on the current solution's feasibility. For the feasible mode, we propose the lift move operator and the lift process to improve the objective value while maintaining feasibility. For the infeasible mode, we propose the breakthrough move and mixed tight move operators to respectively optimize the objective function and satisfy constraints. To apply operators intelligently, we develop a dynamic weighting scheme that balances the priorities of the objective function and constraints. Furthermore, we propose a two-level scoring function structure that hierarchically selects operations, guiding the search toward high-quality feasible solutions. Experiments are conducted on public benchmarks to compare Local-MIP with state-of-the-art MIP solvers in finding high-quality solutions. The results show that Local-MIP significantly outperforms CPLEX, HiGHS, SCIP, and Feasibility Jump while remaining competitive with the commercial solver Gurobi on challenging problems within short time limits. Moreover, Local-MIP establishes 10 new records on MIPLIB open instances.
Keywords:
Mixed Integer Programming
Local Search
Lift Move Operator
Breakthrough Move Operator
Two-Level Scoring Function
Journal
IF:
13.9
Papers:
6.1K
Citations:
1.9W