Abstract
This paper investigates the impact of problem formulation on Dantzig-Wolfe decomposition for the multicommodity network flow problem. These problems are formulated in three ways: origin-destination specific, destination specific, and product specific. The path-based origin-destination specific formulation is equivalent to the tree-based destination specific formulation by a simple transformation. Supersupply and superdemand nodes are appended to the tree-based product specific formulation to create an equivalent path-based product specific formulation. We show that solving the path-based problem formulations by decomposition results in substantially fewer master problem iterations and lower CPU times than by using decomposition on the equivalent tree-based formulations. Computational results on a series of multicommodity network flow problems are presented.
Original language | English (US) |
---|---|
Pages (from-to) | 95-117 |
Number of pages | 23 |
Journal | Mathematical Programming |
Volume | 62 |
Issue number | 1-3 |
DOIs | |
State | Published - Feb 1 1993 |
All Science Journal Classification (ASJC) codes
- Applied Mathematics
- Mathematics(all)
- Safety, Risk, Reliability and Quality
- Management Science and Operations Research
- Software
- Computer Graphics and Computer-Aided Design
- Computer Science(all)