| Article ID: | iaor200969301 |
| Country: | United States |
| Volume: | 51 |
| Issue: | 1 |
| Start Page Number: | 63 |
| End Page Number: | 77 |
| Publication Date: | Jan 2008 |
| Journal: | Networks |
| Authors: | Bompadre Agustn, Orlin James B |
| Keywords: | programming: linear |
We present a new efficient approach for solving the multicommodity flow problem as a sequence of subproblems, each on a very sparse but connected network. We show that each subproblem can be contracted to a problem on a much smaller graph. We then solve these problems using the simplex method. We test the algorithm on benchmark instances, and show its improvement over the usual simplex algorithm.