A decomposition-based pricing procedure for large-scale linear programs: An application to the linear multicommodity flow problem

• 成果类型: Article
• 署名作者: Mamer, JW; McBride, RD
• 署名单位: University of California System; University of California Los Angeles; University of Southern California
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.46.5.693.12042
• 发表日期: 2000
• 页码: 693-709
• 关键词: linear programming; multicommodity flows; optimization

摘要

We propose and test a new pricing procedure for solving large-scale structured linear programs. The procedure interactively solves a relaxed subproblem to identify potential entering basic columns. The subproblem is chosen to exploit special structure, rendering it easy to solve. The effect of the procedure is the reduction of the number of pivots needed to solve the problem. Our approach is motivated by the column-generation approach of Dantzig-Wolfe decomposition. We test our procedure on two sets of multicommodity flow problems. One group of test problems arises in routing telecommunications traffic and the second group is a set of logistics problem which have been widely used to test multicommodity flow algorithms.