Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems

• 成果类型: Article
• 署名作者: Barnhart, C; Hane, CA; Vance, PH
• 署名单位: Massachusetts Institute of Technology (MIT); Auburn University System; Auburn University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.48.2.318.12378
• 发表日期: 2000
• 页码: 318-326

摘要

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.