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

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.