TY - GEN

T1 - A route-based decomposition for the Multi-Commodity <em>k</em>-splittable Maximum Flow Problem

A1 - Gamst,Mette

AU - Gamst,Mette

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - Branch and price

KW - Dantzig-Wolfe Decomposition

KW - Multi-commodity flow

KW - k-splittable

KW - Combinatorial optimization

UR - http://isco12.cs.aueb.gr/

BT - Proceedings

T2 - Proceedings

ER -