TY - JOUR

T1 - Comparing branch-and-price algorithms for the Multi-Commodity k-splittable Maximum Flow Problem

A1 - Gamst,Mette

A1 - Petersen,Bjørn

AU - Gamst,Mette

AU - Petersen,Bjørn

PB - Elsevier BV North-Holland

PY - 2012

Y1 - 2012

N2 - The Multi-Commodity k-splittable Maximum Flow Problem consists in routing as much flow as possible through a capacitated network such that each commodity uses at most k paths and the capacities are satisfied. The problem appears in telecommunications, specifically when considering Multi-Protocol Label Switching. The problem has previously been solved to optimality through branch-and-price. In this paper we propose two exact solution methods both based on an alternative decomposition. The two methods differ in their branching strategy. The first method, which branches on forbidden edge sequences, shows some performance difficulty due to large search trees. The second method, which branches on forbidden and forced edge sequences, demonstrates much better performance. The latter also outperforms a leading exact solution method from the literature. Furthermore, a heuristic algorithm is presented. The heuristic is fast and yields good solution values. (C) 2011 Elsevier B.V. All rights reserved.

AB - The Multi-Commodity k-splittable Maximum Flow Problem consists in routing as much flow as possible through a capacitated network such that each commodity uses at most k paths and the capacities are satisfied. The problem appears in telecommunications, specifically when considering Multi-Protocol Label Switching. The problem has previously been solved to optimality through branch-and-price. In this paper we propose two exact solution methods both based on an alternative decomposition. The two methods differ in their branching strategy. The first method, which branches on forbidden edge sequences, shows some performance difficulty due to large search trees. The second method, which branches on forbidden and forced edge sequences, demonstrates much better performance. The latter also outperforms a leading exact solution method from the literature. Furthermore, a heuristic algorithm is presented. The heuristic is fast and yields good solution values. (C) 2011 Elsevier B.V. All rights reserved.

KW - Heuristic

KW - Combinatorial optimization

KW - Dantzig–Wolfe decomposition

KW - Branch and bound

KW - k-Splittable

KW - Multi-commodity flow

U2 - 10.1016/j.ejor.2011.10.001

DO - 10.1016/j.ejor.2011.10.001

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

VL - 217

SP - 278

EP - 286

ER -