TY - JOUR

T1 - A Dantzig-Wolfe decomposition algorithm for the constrained minimum cost flow problem

AU - Lin, Dung Ying

N1 - Funding Information:
The author would like to acknowledge the National Research Council, Taiwan, ROC, for providing partial funding support under contract number NSC 100-2410-H-006-069-MY3. The contents of the article remain the sole responsibility of the authors.

PY - 2014/7/1

Y1 - 2014/7/1

N2 - Minimum cost flow (MCF) problems are at the core of many optimization problems in numerous domains. In this paper, we extend the well-studied MCF problem by considering an additional resource constraint and propose a Dantzig-Wolfe decomposition algorithm in order to solve this computationally difficult problem. Due to the exponential growth of the columns in the constrained MCF problem, we choose to decompose it into a restricted master problem and a series of pricing problems, so that the columns are generated on an "as-needed" basis. Moreover, as the pricing problem of a constrained MCF is the constrained shortest path (CSP) problem, we design a pseudo-polynomial time label-correcting algorithm to solve the CSP efficiently. To test the proposed solution framework, the developed algorithm is empirically applied to a synthetic network in order to demonstrate its correctness and efficiency. We show the correctness of the theorems, the computational complexity, and the solution methodologies. Finally, we present and discuss computational results and insights.

AB - Minimum cost flow (MCF) problems are at the core of many optimization problems in numerous domains. In this paper, we extend the well-studied MCF problem by considering an additional resource constraint and propose a Dantzig-Wolfe decomposition algorithm in order to solve this computationally difficult problem. Due to the exponential growth of the columns in the constrained MCF problem, we choose to decompose it into a restricted master problem and a series of pricing problems, so that the columns are generated on an "as-needed" basis. Moreover, as the pricing problem of a constrained MCF is the constrained shortest path (CSP) problem, we design a pseudo-polynomial time label-correcting algorithm to solve the CSP efficiently. To test the proposed solution framework, the developed algorithm is empirically applied to a synthetic network in order to demonstrate its correctness and efficiency. We show the correctness of the theorems, the computational complexity, and the solution methodologies. Finally, we present and discuss computational results and insights.

UR - http://www.scopus.com/inward/record.url?scp=84903273455&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84903273455&partnerID=8YFLogxK

U2 - 10.1080/02533839.2013.815010

DO - 10.1080/02533839.2013.815010

M3 - Article

AN - SCOPUS:84903273455

VL - 37

SP - 659

EP - 669

JO - Chung-kuo Kung Ch'eng Hsueh K'an/Journal of the Chinese Institute of Engineers

JF - Chung-kuo Kung Ch'eng Hsueh K'an/Journal of the Chinese Institute of Engineers

SN - 0253-3839

IS - 5

ER -