We propose a new cutting plane algorithm for Integer Linear Programming, which we refer to as the bound-optimal cutting plane method. The algorithm amounts to simultaneously generating k cuts which, when added to the linear programming relaxation, yield the (provably) largest bound improvement. We show that, in the general case, the corresponding cut generating problem can be cast as a Quadratically Constrained Quadratic Program. We also show that, for a large family of cuts, the latter can be reformulated as a Mixed-Integer Linear Program. We present computational experiments on the generation of bound-optimal stable set and cover inequalities for the max clique and knapsack problems. They show that, with respect to standard algorithms, the bound-optimal cutting plane method allows for a substantial reduction in the number of cuts and iterations needed to achieve either a given bound or an optimal solution.

(2015). On the generation of cutting planes which maximize the bound improvement . Retrieved from http://hdl.handle.net/10446/229382

On the generation of cutting planes which maximize the bound improvement

Coniglio, Stefano;
2015

Abstract

We propose a new cutting plane algorithm for Integer Linear Programming, which we refer to as the bound-optimal cutting plane method. The algorithm amounts to simultaneously generating k cuts which, when added to the linear programming relaxation, yield the (provably) largest bound improvement. We show that, in the general case, the corresponding cut generating problem can be cast as a Quadratically Constrained Quadratic Program. We also show that, for a large family of cuts, the latter can be reformulated as a Mixed-Integer Linear Program. We present computational experiments on the generation of bound-optimal stable set and cover inequalities for the max clique and knapsack problems. They show that, with respect to standard algorithms, the bound-optimal cutting plane method allows for a substantial reduction in the number of cuts and iterations needed to achieve either a given bound or an optimal solution.
Coniglio, Stefano; Tieves, Martin
File allegato/i alla scheda:
File Dimensione del file Formato  
Coniglio_2015_SEA.pdf

Solo gestori di archivio

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