A Branch and Price algorithm for the kk-splittable maximum flow problem

The Maximum Flow Problem with flow width constraints is an NP-hard problem. Two models are proposed: the first model is a compact node-arc model using two flow conservation blocks per path. For each path, one block defines the path while the other one sends the right amount of flow on it. The second model is an extended arc-path model, obtained from the first model after a Dantzig–Wolfe reformulation. It is an extended model as it relies on the set of all the paths between the source and the sink nodes. Some symmetry breaking constraints are used to improve the model. A Branch and Price algorithm is proposed to solve the problem. The column generation procedure reduces to the computation of a shortest path whose cost depends on weights on the arcs and on the path capacity. A polynomial-time algorithm is proposed to solve this subproblem. Computational results are shown on a set of medium-sized instances to show the effectiveness of our approach.