Mixed integer optimization is a powerful tool for modeling many optimization prob- lems arising from real-world applications. Finding a first feasible solution represents the first step for several mixed integer programming (MIP) sol vers. The feasibility pum p is a heuristic for finding feasible solutions to mixed integer linear programming (MILP) problems which is effective 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 define 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 dy- namically combining two different merit functions. Finally, we define 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 effectiveness of our approach.

A new class of functions for measuring solution integrality in the feasibility pump approach / DE SANTIS, MARIANNA; LUCIDI, Stefano; Francesco Rinaldi. - In: SIAM JOURNAL ON OPTIMIZATION. - ISSN 1052-6234. - STAMPA. - 23:(2013), pp. 1575-1606. [10.1137/110855351]

A new class of functions for measuring solution integrality in the feasibility pump approach

DE SANTIS, MARIANNA;LUCIDI, Stefano;
2013

Abstract

Mixed integer optimization is a powerful tool for modeling many optimization prob- lems arising from real-world applications. Finding a first feasible solution represents the first step for several mixed integer programming (MIP) sol vers. The feasibility pum p is a heuristic for finding feasible solutions to mixed integer linear programming (MILP) problems which is effective 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 define 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 dy- namically combining two different merit functions. Finally, we define 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 effectiveness of our approach.
2013
23
1575
1606
DE SANTIS, MARIANNA; LUCIDI, Stefano; Francesco Rinaldi
File in questo prodotto:
File Dimensione Formato  
DeSantis_A-new-class_2013.pdf

Accesso chiuso

Licenza: Tutti i diritti riservati
Dimensione 1.07 MB
Formato Adobe PDF
1.07 MB Adobe PDF   Richiedi una copia

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1350094
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 20
  • ???jsp.display-item.citation.isi??? 16
social impact