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

Publication: Research - peer-reviewJournal article – Annual report year: 2012

Documents

DOI

View graph of relations

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.
Original languageEnglish
JournalEuropean Journal of Operational Research
Publication date2012
Volume217
Issue2
Pages278-286
ISSN0377-2217
DOIs
StatePublished
CitationsWeb of Science® Times Cited: 2

Keywords

  • Heuristic, Combinatorial optimization, Dantzig–Wolfe decomposition, Branch and bound, k-Splittable, Multi-commodity flow
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

Download statistics

No data available

ID: 6418540