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

Dung Ying Lin

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

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/Chung-kuo Kung Ch'eng Hsuch K'an
Volume37
Issue number5
DOIs
Publication statusPublished - 2014 Jul 1

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint 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