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

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

Standard

A route-based decomposition for the Multi-Commodity k-splittable Maximum Flow Problem. / Gamst, Mette.

Proceedings. 2012.

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

Harvard

APA

CBE

MLA

Vancouver

Author

Gamst, Mette / A route-based decomposition for the Multi-Commodity k-splittable Maximum Flow Problem.

Proceedings. 2012.

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

Bibtex

@inbook{e70010d4aa0c493dbe7a39cf00825215,
title = "A route-based decomposition for the Multi-Commodity k-splittable Maximum Flow Problem",
keywords = "Branch and price, Dantzig-Wolfe Decomposition, Multi-commodity flow, k-splittable, Combinatorial optimization",
author = "Mette Gamst",
year = "2012",
booktitle = "Proceedings",

}

RIS

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 -