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

Dung Ying Lin

研究成果: Article同行評審

3 引文 斯高帕斯(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.

原文English
頁(從 - 到)659-669
頁數11
期刊Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A
37
發行號5
DOIs
出版狀態Published - 2014 7月 1

All Science Journal Classification (ASJC) codes

  • 工程 (全部)

指紋

深入研究「A Dantzig-Wolfe decomposition algorithm for the constrained minimum cost flow problem」主題。共同形成了獨特的指紋。

引用此