期刊名称：Department of Computer and System Sciences Antonio Ruberti Technical Reports
印刷版ISSN：2035-5750
出版年度：2011
卷号：3
期号：8
语种：English
出版社：Department of Computer and System Sciences Antonio Ruberti. Sapienza, Università di Roma
摘要：Mixed-Integer optimization is a powerful tool for modeling many optimization problems arising from real-world applications. Finding a rst feasible solution represents the rst step for several MIP solvers. The Feasibility pump is a heuristic for nding feasible solutions to mixed integer linear problems which is eective even when dealing with hard MIP instances. In this work, we start by interpreting the Feasibility Pump as a Frank-Wolfe method applied to a nonsmooth concave merit function. Then, we dene a general class of functions that can be included in the Feasibility Pump scheme for measuring solution integrality and we identify some merit functions belonging to this class. We further extend our approach by dynamically combining two dierent merit functions. Finally, we dene a new version of the Feasibility Pump algorithm, which includes the original version of the Feasibility Pump as a special case, and we present computational results on binary MILP problems showing the eectiveness of our approach.
