A route-based decomposition for the Multi-Commodity k-splittable Maximum Flow Problem

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2012

Documents

View graph of relations

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.
Original languageEnglish
Title of host publicationProceedings
Number of pages4
Publication date2012
StatePublished

Conference

Conference2nd International Symposium on Combinatorial Optimization (ISCO 2012)
CountryGreece
CityAthens
Period17/04/1221/04/12

Keywords

  • Branch and price, Dantzig-Wolfe Decomposition, Multi-commodity flow, k-splittable, Combinatorial optimization
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: 7873269