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

Dung Ying Lin

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)659-669
Number of pages11
JournalJournal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A
Issue number5
Publication statusPublished - 2014 Jul 1

All Science Journal Classification (ASJC) codes

  • Engineering(all)


Dive into the research topics of 'A Dantzig-Wolfe decomposition algorithm for the constrained minimum cost flow problem'. Together they form a unique fingerprint.

Cite this