A decomposition based on path sets for the Multi-Commodity k-splittable Maximum Flow Problem

The Multi-Commodity k-splittable Maximum Flow Problem routes flow through a capacitated graph such that each commodity uses at most k paths and such that the total amount of routed flow is maximized. The problem appears in telecommunications, specifically when considering Multi-Protocol Label Switching. In the literature, the problem is solved to optimality using branch-and-price algorithms built on path-based Dantzig-Wolfe decompositions. This paper proposes a new branch-and-price algorithm built on a path set-based Dantzig-Wolfe decomposition. A path set consists of up to k paths, each carrying a certain amount of flow. The new branch-and-price algorithm is implemented and compared to the leading algorithms in the literature. Results for the proposed method are competitive and the method even has best performance on some instances. However, the results also indicate some scaling issues.