Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems

Cynthia Barnhart (), Christopher A. Hane () and Pamela H. Vance ()
Additional contact information
Cynthia Barnhart: Massachusetts Institute of Technology, Center for Transportation Studies, Cambridge, Massachusetts 02139
Christopher A. Hane: CAPS Logistics, Atlanta, Georgia 30334
Pamela H. Vance: Auburn University, Industrial and Systems Engineering, Auburn, Alabama 36849

Operations Research, 2000, vol. 48, issue 2, 318-326

Abstract: We present a column-generation model and branch-and-price-and-cut algorithm for origin-destination integer multicommodity flow problems. The origin-destination integer multicommodity flow problem is a constrained version of the linear multicommodity flow problem in which flow of a commodity (defined in this case by an origin-destination pair) may use only one path from origin to destination. Branch-and-price-and-cut is a variant of branch-and-bound, with bounds provided by solving linear programs using column-and-cut generation at nodes of the branch-and-bound tree. Because our model contains one variable for each origin-destination path, for every commodity, the linear programming relaxations at nodes of the branch-and-bound tree are solved using column generation, i.e., implicit pricing of nonbasic variables to generate new columns or to prove LP optimality. We devise a new branching rule that allows columns to be generated efficiently at each node of the branch-and-bound tree. Then, we describe cuts (cover inequalities) that can be generated at each node of the branch-and-bound tree. These cuts help to strengthen the linear programming relaxation and to mitigate the effects of problem symmetry. We detail the implementation of our combined column-and-cut generation method and present computational results for a set of test problems arising from telecommunications applications. We illustrate the value of our branching rule when used to find a heuristic solution and compare branch-and-price and branch-and-price-and-cut methods to find optimal solutions for highly capacitated problems.

Keywords: Networks/graphs: multicommodity; Programming; integer: branch-and-bound; Programming; linear: column generation (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (71)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.48.2.318.12378 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:48:y:2000:i:2:p:318-326

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().