A route-based decomposition 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 routedflow is maximized. This paper proposes a branch-and-price algorithm based on a route-based Dantzig-Wolfe decomposition, where a route consists of up to k paths.

Computational results show that the new algorithm has best performance on seven benchmark instances and is capable of solving two previously unsolved instances.