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

Publication: Research - peer-review › Article in proceedings – Annual report year: 2012

### Standard

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

Publication: Research - peer-review › Article in proceedings – Annual report year: 2012

### Harvard

*k*-splittable Maximum Flow Problem. in

*Proceedings.*

### APA

*k*-splittable Maximum Flow Problem. In

*Proceedings*

### CBE

*k*-splittable Maximum Flow Problem. In Proceedings.

### MLA

*k*-splittable Maximum Flow Problem".

*Proceedings.*2012.

### Vancouver

*k*-splittable Maximum Flow Problem. In Proceedings. 2012.

### Author

### Bibtex

}

### RIS

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

ER -