A new class of functions for measuring solution integrality in the Feasibility Pump approach

Marianna De Santis (), Stefano Lucidi () and Francesco Rinaldi ()
Additional contact information
Marianna De Santis: Dipartimento di Informatica e Sistemistica "Antonio Ruberti" Sapienza, Universita' di Roma
Stefano Lucidi: Dipartimento di Informatica e Sistemistica "Antonio Ruberti" Sapienza, Universita' di Roma
Francesco Rinaldi: Dipartimento di Informatica e Sistemistica "Antonio Ruberti" Sapienza, Universita' di Roma

No 2011-08, DIS Technical Reports from Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza"

Abstract: 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.

Keywords: Mixed integer programming; Concave penalty functions; Frank-Wolfe algorithm; Feasibility Problem (search for similar items in EconPapers)
Date: 2011
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.dis.uniroma1.it/~bibdis/RePEc/aeg/wpaper/2011-08.pdf First version 2011 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:aeg:wpaper:2011-8

Access Statistics for this paper

More papers in DIS Technical Reports from Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza" Contact information at EDIRC.
Bibliographic data for series maintained by Antonietta Angelica Zucconi ( this e-mail address is bad, please contact ).