Multicommodity network flows: The impact of formulation on decomposition |
| |
Authors: | Kim L. Jones Irvin J. Lustig Judith M. Farvolden Warren B. Powell |
| |
Affiliation: | (1) Department of Civil Engineering and Operations Research, Program in Statistics and Operations Research, Princeton University, Princeton, NJ, USA;(2) Department of Industrial Engineering, University of Toronto, Ont., Canada;(3) Department of Civil Engineering and Operations Research, School of Engineering and Applied Sciences, Princeton University, 08544 Princeton, NJ, USA |
| |
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.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|