A fix-propagate-repair heuristic for mixed integer programming

  • We describe a diving heuristic framework based on constraint propagation for mixed integer linear programs. The proposed approach is an extension of the common fix-and-propagate scheme, with the addition of solution repairing after each step. The repair logic is loosely based on the WalkSAT strategy for boolean satisfiability. Different strategies for variable ranking and value selection, as well as other options, yield different diving heuristics. The overall method is relatively inexpensive, as it is basically LP-free: the full linear programming relaxation is solved only at the beginning (and only for the ranking strategies that make use of it), while additional, typically much smaller, LPs are only used to compute values for the continuous variables (if any), once at the bottom of a dive. While individual strategies are not very robust in finding feasible solutions on a heterogeneous testbed, a portfolio approach proved quite effective. In particular, it could consistently find feasible solutions in 189 out of 240 instances from the public MIPLIB 2017 benchmark testbed, in a matter of a few seconds of runtime. The framework has also been implemented inside the commercial MIP solver Xpress and shown to give a small performance improvement in time to optimality on a large internal heterogeneous testbed.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Domenico Salvagnin, Roberto Roberti, Matteo Fischetti
DOI:https://doi.org/10.1007/s12532-024-00269-5
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2024
Volume:17
Issue:1
Page Number:29
First Page:111
Last Page:139
Mathematical Programming Computation :MPC 2025 - Issue 1
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.