Premium
Solving the undirected multicommodity flow problem using a shortest path‐based pricing algorithm
Author(s) -
McBride Richard D.,
Mamer John W.
Publication year - 2001
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.1035
Subject(s) - shortest path problem , mathematical optimization , flow network , multi commodity flow problem , simplex algorithm , dijkstra's algorithm , piecewise linear function , mathematics , linear programming , undirected graph , path (computing) , simplex , computer science , algorithm , graph , combinatorics , geometry , programming language
The undirected multicommodity flow problem is encountered in the solution to traffic‐scheduling problems related to computer, communication, railroad, and other networks. We show how to formulate this problem as a piecewise linear optimization problem (with piecewise linear convex functions in both the objective and the constraints). We discuss how EMNET, a primal basis partitioning simplex algorithm, was modified so as to efficiently solve these problems using a pricing procedure that we call “shortest path pricing.” Extremely good solution times for some very large problems are presented. The solutions are not only obtained quickly, but also with a fraction of the number of pivots that are needed for the standard simplex method. © 2001 John Wiley & Sons, Inc.