In cutting plane-based methods, the question of how to generate the “best possible” cuts is a central and critical issue. We propose a bi-criteria separation problem for generating valid inequalities that simultaneously maximizes the cut violation and a measure of the diversity between the new cut and the previously generated cut(s). We focus on problems with cuts having 0-1 coefficients, and use the 1-norm as diversity measure. In this context, the bi-criteria separation amounts to solving the standard single-criterion separation problem (maximizing violation) with different coefficients in the objective function. We assess the impact of this general approach on two challenging combinatorial optimization problems, namely the Min Steiner Tree problem and the Max Clique problem. Computational experiments show that the cuts generated by the bi-criteria separation are much stronger than those obtained by just maximizing the cut violation, and allow to close a larger fraction of the gap in a smaller amount of time.

(2010). Improving Cutting Plane Generation with 0-1 Inequalities by Bi-criteria Separation . Retrieved from http://hdl.handle.net/10446/229357

Improving Cutting Plane Generation with 0-1 Inequalities by Bi-criteria Separation

Coniglio, Stefano;
2010

Abstract

In cutting plane-based methods, the question of how to generate the “best possible” cuts is a central and critical issue. We propose a bi-criteria separation problem for generating valid inequalities that simultaneously maximizes the cut violation and a measure of the diversity between the new cut and the previously generated cut(s). We focus on problems with cuts having 0-1 coefficients, and use the 1-norm as diversity measure. In this context, the bi-criteria separation amounts to solving the standard single-criterion separation problem (maximizing violation) with different coefficients in the objective function. We assess the impact of this general approach on two challenging combinatorial optimization problems, namely the Min Steiner Tree problem and the Max Clique problem. Computational experiments show that the cuts generated by the bi-criteria separation are much stronger than those obtained by just maximizing the cut violation, and allow to close a larger fraction of the gap in a smaller amount of time.
Amaldi, Edoardo; Coniglio, Stefano; Gualandi, Stefano
File allegato/i alla scheda:
File Dimensione del file Formato  
sea-2010.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 297.72 kB
Formato Adobe PDF
297.72 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/229357
Citazioni
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 8
social impact