Ítem


An Efficient Local Search Solver for Mixed Integer Programming

Peng Lin from a chinese university, tells that a mixed integer programming (MIP) is a fundamental model in operations research. Local search is a powerful method for solving hard problems, but the development of local search solvers for MIP still needs to be explored. This work develops an efficient local search solver for solving MIP, called Local-MIP. We propose two new operators for MIP to adaptively modify variables for optimizing the objective function and satisfying constraints, respectively. Furthermore, we design a new weighting scheme to dynamically balance the priority between the objective function and each constraint, and propose a two-level scoring function structure to hierarchically guide the search for high-quality feasible solutions. Experiments are conducted on seven public benchmarks to compare Local-MIP with state-of-the-art MIP solvers, which demonstrate that Local-MIP significantly outperforms CPLEX, HiGHS, SCIP and Feasibility Jump, and is competitive with the most powerful commercial solver Gurobi. Moreover, Local-MIP establishes 4 new records for MIPLIB open instances

7765.mp4 7765.mp3

Universitat de Girona. Departament d’Informàtica, Matemàtica Aplicada i Estadística

Altres contribucions: Universitat de Girona. Departament d’Informàtica, Matemàtica Aplicada i Estadística
Autor: Lin, Peng
Zou, Mengchuan
Cai, Shaowei
Data: 3 setembre 2024
Resum: Peng Lin from a chinese university, tells that a mixed integer programming (MIP) is a fundamental model in operations research. Local search is a powerful method for solving hard problems, but the development of local search solvers for MIP still needs to be explored. This work develops an efficient local search solver for solving MIP, called Local-MIP. We propose two new operators for MIP to adaptively modify variables for optimizing the objective function and satisfying constraints, respectively. Furthermore, we design a new weighting scheme to dynamically balance the priority between the objective function and each constraint, and propose a two-level scoring function structure to hierarchically guide the search for high-quality feasible solutions. Experiments are conducted on seven public benchmarks to compare Local-MIP with state-of-the-art MIP solvers, which demonstrate that Local-MIP significantly outperforms CPLEX, HiGHS, SCIP and Feasibility Jump, and is competitive with the most powerful commercial solver Gurobi. Moreover, Local-MIP establishes 4 new records for MIPLIB open instances
7765.mp4 7765.mp3
Format: audio/mpeg
video/mp4
Accés al document: http://hdl.handle.net/10256.1/7765
Llenguatge: eng
Editor: Universitat de Girona. Departament d’Informàtica, Matemàtica Aplicada i Estadística
Col·lecció: 30th International Conference on Principles and Practice of Constraint Programming
Drets: Attribution-NonCommercial-ShareAlike 4.0 International
URI Drets: http://creativecommons.org/licenses/by-nc-sa/4.0/
Matèria: Programació per restriccions (Informàtica) -- Congressos
Constraint programming (Computer science) -- Congresses
Títol: An Efficient Local Search Solver for Mixed Integer Programming
Tipus: info:eu-repo/semantics/lecture
Repositori: DUGiMedia

Matèries

Autors