TR-2012-09

Algorithms for multiplayer multicommodity flow problems

Attila Bernáth, Tamás Király, Erika Renáta Bérczi-Kovács, Gergely Mádi-Nagy, Gyula Pap, Júlia Pap, Jácint Szabó, László Végh

Published in:
Central European Journal of Operations Research 21 (2013), 699-712.

We investigate the Multiplayer Multicommodity Flow Problem (MMFP): several players have different networks and commodities over a common node set. Pairs of players have contracts where one of them agrees to route the flow of the other player (up to a given capacity) between two specified nodes. In return, the second player pays an amount proportional to the flow value.
 
We show that the social optimum can be computed by linear programming, and we propose algorithms based on column generation and Lagrangian relaxation. In contrast, we prove that it is hard to decide if an equilibrium solution exists, although some natural conditions guarantee its existence.

Bibtex entry:

@techreport{egres-12-09,

AUTHOR	=	{Bern{\'a}th, Attila and Kir{\'a}ly, Tam{\'a}s and B{\'e}rczi-Kov{\'a}cs Ren{\'a}ta, Erika and M{\'a}di-Nagy, Gergely and Pap, Gyula and Pap, J{\'u}lia and Szab{\'o}, J{\'a}cint and V{\'e}gh, L{\'a}szl{\'o}},
TITLE	=	{Algorithms for multiplayer multicommodity flow problems},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2012},
NUMBER	=	{TR-2012-09}

}