Item


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鈥橧nform脿tica, Matem脿tica Aplicada i Estad铆stica

Other contributions: Universitat de Girona. Departament d鈥橧nform脿tica, Matem脿tica Aplicada i Estad铆stica
Author: Lin, Peng
Zou, Mengchuan
Cai, Shaowei
Date: 2024 September 3
Abstract: 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
Document access: http://hdl.handle.net/10256.1/7765
Language: eng
Publisher: Universitat de Girona. Departament d鈥橧nform脿tica, Matem脿tica Aplicada i Estad铆stica
Collection: 30th International Conference on Principles and Practice of Constraint Programming
Rights: Attribution-NonCommercial-ShareAlike 4.0 International
Rights URI: http://creativecommons.org/licenses/by-nc-sa/4.0/
Subject: Programaci贸 per restriccions (Inform脿tica) -- Congressos
Constraint programming (Computer science) -- Congresses
Title: An Efficient Local Search Solver for Mixed Integer Programming
Type: info:eu-repo/semantics/lecture
Repository: DUGiMedia

Subjects

Authors