.png){kind=icon}
Return
A fix-propagate-repair heuristic for mixed integer programming
.png){kind=icon}
OA
AI
DOI：10.1007/s12532-024-00269-5.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Mixed integer programming
Heuristics
Solution repair
Constraint propagation
Journal
IF:
3.6
Papers:
202
Citations:
1.9K
Organization
Cited Papers
Recovery of salinity gradient energy in desalination plants by reverse electrodialysis.png)
Desalination
OAAI
DesalinationIF0
OAAIShareSaveAlginate surfactant derivatives as an ecofriendly corrosion inhibitor for carbon steel in acidic environmentsRSC Advances
RSC AdvancesIF0
PREAI
ShareSave
View more