In this paper we present a column generation model and a branch-and-price algorithm for a multicommodity k-splittable flow problem. The k-splittable flow is an extension of the unsplittable flow. It has been introduced by Baier, Köhler and Skutella in [4]. This flow can be split into at most k paths. The k-splittable flow is used to study path limitation constraints in classical flow problems. In this paper we consider only the maximal k-splittable flow problem. First we formulate this problem with two sets of variables for each one of the k paths: path design variables and flow variables. This leads to a large linear mixed integer program with two types of variables. The subproblem is not exactly an unsplittable flow problem since the amount of flow is not known. This degree of freedom complexifies this problem. Moreover the flow conservation constraint alone does not ensure that the decision variables define a single path since any set of directed cycles satisfies this constraint. So an additional constraint is put on each nodes cocycle. It allows only sets of disjoint directed cycles.

Next we present a path decomposition on this model, which gives us an exponential edge-path model. Then a Branch-and-Price algorithm is applied. The branching strategy is based on the work of Barnhart and al. for the integer multicommodity flow problem [5]. The column generation subproblem can be seen as a shortest path problem with "high" enough capacity. We propose a polynomial time algorithm to solve this subproblem. Computational results are improved by introducing strategies like variable ordering and storing paths in a pool. Finally numerical results are reported for the different strategies and with a direct MIP approach.

@inproceedings{Truffot05b,
 author = {J{\'e}r{\^o}me Truffot and Christophe Duhamel and Philippe Mahey},
 title = {{Using Branch-and-Price to Solve Multicommodity k-Splittable
              Flow Problems}},
 booktitle = {The Proceedings of 2005 International Network Optimisation 
                    Conference},
 dates = {20-23 mars}
 year = {2005},
 pages = {811--816},
 location = {Lisbonne, Portugal},
}