In cutting plane methods, the question of how to generate the best possible set of cuts is both central and crucial. We propose a lexicographic multi-objective cutting plane generation scheme that generates, among all the maximally violated valid inequalities of a given family, an inequality that is undominated and maximally diverse w.r.t. the cuts that were previously found. By optimizing a diversity measure, we introduce a form of coordination between successive cuts. Our focus is on valid inequalities with 0-1 coefficients in the left-hand side and a constant right-hand side, which encompasses several families of valid inequalities. As cut diversity measure, we consider an aggregate of the 1-norm distances w.r.t. the normal vectors of the previous cuts. In this case, our lexicographic multi-objective separation problem reduces to the standard separation problem with different values for the objective function coefficients. The impact of our coordinated cutting plane generation scheme is assessed in a pure cutting plane setting when separating Stable Set and Cut Set inequalities for, respectively, the Max Clique and Min Steiner Tree problems. Compared to the standard separation of undominated maximally violated cuts, we close the same fraction of the duality gap in a considerably smaller number of rounds and cuts. The potential of our scheme is also indicated by the results obtained in a cut-and-branch setting for Max Clique, where cut coordination allows for a substantial reduction, on average, of the number of branch-and-bound nodes.

(2014). Coordinated cutting plane generation via multi-objective separation [journal article - articolo]. In MATHEMATICAL PROGRAMMING. Retrieved from http://hdl.handle.net/10446/229300

Coordinated cutting plane generation via multi-objective separation

Coniglio, Stefano;
2014

Abstract

In cutting plane methods, the question of how to generate the best possible set of cuts is both central and crucial. We propose a lexicographic multi-objective cutting plane generation scheme that generates, among all the maximally violated valid inequalities of a given family, an inequality that is undominated and maximally diverse w.r.t. the cuts that were previously found. By optimizing a diversity measure, we introduce a form of coordination between successive cuts. Our focus is on valid inequalities with 0-1 coefficients in the left-hand side and a constant right-hand side, which encompasses several families of valid inequalities. As cut diversity measure, we consider an aggregate of the 1-norm distances w.r.t. the normal vectors of the previous cuts. In this case, our lexicographic multi-objective separation problem reduces to the standard separation problem with different values for the objective function coefficients. The impact of our coordinated cutting plane generation scheme is assessed in a pure cutting plane setting when separating Stable Set and Cut Set inequalities for, respectively, the Max Clique and Min Steiner Tree problems. Compared to the standard separation of undominated maximally violated cuts, we close the same fraction of the duality gap in a considerably smaller number of rounds and cuts. The potential of our scheme is also indicated by the results obtained in a cut-and-branch setting for Max Clique, where cut coordination allows for a substantial reduction, on average, of the number of branch-and-bound nodes.
articolo
Amaldi, Edoardo; Coniglio, Stefano; Gualandi, Stefano
(2014). Coordinated cutting plane generation via multi-objective separation [journal article - articolo]. In MATHEMATICAL PROGRAMMING. Retrieved from http://hdl.handle.net/10446/229300
File allegato/i alla scheda:
File Dimensione del file Formato  
coordinated-cuts-MPA-14.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 333.9 kB
Formato Adobe PDF
333.9 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/229300
Citazioni
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 13
social impact