This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Andreello, G. Articles by Fischetti, M. Search for Related Content

Embedding {0, }-Cuts in a Branch-and-Cut Framework: A Computational Study

DEI, Università di Padova, Via Gradenigo, 6/A, I-35131 Padova, Italy
DEIS, Università di Bologna, Viale Risorgimento, 2, I-40136 Bologna, Italy
DEI, Università di Padova, Via Gradenigo, 6/A, I-35131 Padova, Italy
a.beppe{at}libero.it
acaprara{at}deis.unibo.it
fisch{at}dei.unipd.it

Embedding cuts into a branch-and-cut framework is a delicate task, especially when a large set of cuts is available. In this paper we describe a separation heuristic for {0, } cuts, a special case of Chvátal-Gomory cuts, that tends to produce many violated inequalities within relatively short time. We report computational results on a large testbed of integer linear programming (ILP) instances of combinatorial problems including satisfiability, max-satisfiability, and linear ordering problems, showing that a careful cut-selection strategy produces a considerable speedup with respect to the cases in which either the separation heuristic is not used at all, or all of the cuts it produces are added to the LP relaxation.

Key words: programming; integer; algorithms; cutting plane; programming; integer; applications
History: received May 2004; revised January 2005; accepted July 2005.

This article has been cited by other articles:

				W. Cook, D. G. Espinoza, and M. Goycoolea Computing with Domino-Parity Inequalities for the Traveling Salesman Problem (TSP) INFORMS Journal on Computing, January 1, 2007; 19(3): 356 - 365. [Abstract] [PDF]