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

Mette Gamst

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

Mette Gamst

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

171 Downloads (Pure)

Abstract

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 language	English
Title of host publication	Proceedings
Number of pages	4
Publication date	2012
Publication status	Published - 2012
Event	2nd International Symposium on Combinatorial Optimization (ISCO 2012) - Athens, Greece Duration: 17 Apr 2012 → 21 Apr 2012

Conference

Conference	2nd International Symposium on Combinatorial Optimization (ISCO 2012)
Country/Territory	Greece
City	Athens
Period	17/04/2012 → 21/04/2012

Keywords

Branch and price
Dantzig-Wolfe Decomposition
Multi-commodity flow
k-splittable
Combinatorial optimization

Access to Document

A route based decompositionFinal published version, 202 KB

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

OpenUrl availability

Full text

Cite this

@inproceedings{e70010d4aa0c493dbe7a39cf00825215,

title = "A route-based decomposition for the Multi-Commodity k-splittable Maximum Flow Problem",

abstract = "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.",

keywords = "Branch and price, Dantzig-Wolfe Decomposition, Multi-commodity flow, k-splittable, Combinatorial optimization",

author = "Mette Gamst",

year = "2012",

language = "English",

booktitle = "Proceedings",

note = "2nd International Symposium on Combinatorial Optimization (ISCO 2012) ; Conference date: 17-04-2012 Through 21-04-2012",

}

TY - GEN

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

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

M3 - Article in proceedings

BT - Proceedings

T2 - 2nd International Symposium on Combinatorial Optimization (ISCO 2012)

Y2 - 17 April 2012 through 21 April 2012

ER -

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

Abstract

Conference

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this