This Article Full Text (PDF) 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 Google Scholar Articles by Fischetti, M. Articles by Salvagnin, D.

Pruning Moves

Dipartimento di Ingegneria dell'Informazione, University of Padova, 35131 Padova, Italy
Dipartimento di Matematica Pura ed Applicata, University of Padova, 35121 Padova, Italy
matteo.fischetti{at}unipd.it
salvagni{at}math.unipd.it

The concept of dominance among nodes of a branch-and-bound tree, although known for a long time, is typically not exploited by general-purpose mixed-integer linear programming (MILP) codes. The starting point of our work was the general-purpose dominance procedure proposed in the 1980s by Fischetti and Toth, where the dominance test at a given node of the branch-and-bound tree consists of the (possibly heuristic) solution of a restricted MILP only involving the fixed variables. Both theoretical and practical issues concerning this procedure are analyzed, and important improvements are proposed. In particular, we use the dominance test not only to fathom the current node of the tree, but also to derive variable configurations called "nogoods" and, more generally, "improving moves." These latter configurations, which we rename "pruning moves" so as to stress their use in a node-fathoming context, are used during the enumeration to fathom large sets of dominated solutions in a computationally effective way. Computational results on a testbed of MILP instances whose structure is amenable to dominance are reported, showing that the proposed method can lead to a considerable speedup when embedded in a commercial MILP solver.

Key words: mixed-integer programming; constraint programming; dominance procedure; nogoods
History: received May 2008; revised January 2009; accepted March 2009.