A Decomposition-Based Pricing Procedure for Large-Scale Linear Programs: An Application to the Linear Multicommodity Flow Problem
Authors:
- 1 May 2000
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Management Science
- Vol. 46 (5) , 693-709
Abstract
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.Keywords
This publication has 14 references indexed in Scilit:
- An implementation of linear and nonlinear multicommodity network flowsEuropean Journal of Operational Research, 1996
- Gigaflops in linear programmingOperations Research Letters, 1996
- A column generation and partitioning approach for multi-commodity flow problemsTelecommunication Systems, 1994
- Interior Point Methods for Linear Programming: Just Call Newton, Lagrange, and Fiacco and McCormick!Interfaces, 1990
- An Empirical Evaluation of the KORBX® Algorithms for Military Airlift ApplicationsOperations Research, 1990
- A simplex algorithm for piecewise-linear programming II: Finiteness, feasibility and degeneracyMathematical Programming, 1988
- A simplex algorithm for piecewise-linear programming I: Derivation and proofMathematical Programming, 1985
- Solving embedded generalized network problemsEuropean Journal of Operational Research, 1985
- Solving Generalized NetworksManagement Science, 1984
- New Finite Pivoting Rules for the Simplex MethodMathematics of Operations Research, 1977