Capacited Linear Multicommodity Flow Problems
This web page provides some class of instances used in [BdMV04] to solve capacited linear multicommodity flow problem (static formulation). The dataset format is described in format.txt. The best value, which is indicated in the following tables, is a certified upper bound and the relative gap between the best value and the lower bound is less than 10^{5}.
Planar instances have been generated by Di Yuan to simulate the problems arising in telecommunications problems. Nodes are randomly chosen as points in the plane, and arcs link neighbour nodes in such a way that the resulting graph is planar. Commodities are pair of origin and destination nodes, randomly chosen. Demands and capacities are uniformly distributed in given intervals.
The Planar instances descibed in the following table, are used in [LY04] and are provided in the web site :
http://www.di.unipi.it/di/groups/optimize/Data/MMCF.html
Planar 30  Planar 50  Planar 80  Planar 100  Planar 150  Planar 300  Planar 500  Planar 800  Planar 1000  Planar2500  
# Nodes  30  50  80  100  150  300  500  800  1000  2500 
# Arcs  150  250  440  532  850  1680  2842  4388  5200  12990 
# Comm.  92  267  543  1085  2239  3584  3525  12756  20026  81430 
Best Value  4.43508e7  1.22200e8  1.82438e8  2.31340e8  5.48089e8  6.89982e8  4.81984e8  1.16737e8  3.44962e9  1.26624e10 
The Grid netwoks have a logical grid structure. This grid structure is used in some telecommunications problems.The Grid instances descibed in the following table are solved in [LY04] and are also provided in the website :
http://www.di.unipi.it/di/groups/optimize/Data/MMCF.html
# Nodes  # Arcs  # Comm. 
Best Value 

Grid 1  25  80  50  8.27323e5 
Grid 2  25  80  100  1.70538e6 
Grid 3  100  360  50  1.52464e6 
Grid 4  100  360  100  3.03170e6 
Grid 5  225  840  100  5.04970e6 
Grid 6  225  840  200  1.04007e7 
Grid 7  400  1520  400  2.58641e7 
Grid 8  625  2400  500  4.17113e7 
Grid 9  625  2400  1000  8.26533e7 
Grid 10  625  2400  2000  1.64111e8 
Grid 11  625  2400  3000  3.29259e8 
Grid 12  900  3480  6000  5.77189e8 
Grid 13  900  3480  12000  1.15932e9 
Grid 14  1225  4760  16000  1.80268e9 
Grid 15  1225  4760  32000  3.59353e9 
The SiouxFalls, Winnipeg and Barcelona problems are solved in [LY04] by T. Larsson and Di Yuan. They reduced the commodity demands of Winnipeg and Barcelona (divided by resp. 2.7, and 3) to make these problems feasible with respect to the static capacited linear formulation. The demands of Chicago sketch, Chicago region and Philadelphia problems had also to be scaled to solve this problem formulation . We divided the demands by (resp.) 2.5, 6, and 7. The dataets of the last three ones are provided in the website :
http://www.bgu.ac.il/~bargera/tntp/
# Nodes  # Arcs  # Comm. 
Best Value 

SiouxFalls  24  76  528  3.20184e5 
Winnipeg  1'052  2'836  4'344  2.94065e7 
Barcelona  1'020  2'522  7'922  3.89400e7 
Chicago sketch  933  2'950  93'513  5.49053e1 
Chicago region  12'982  39'018  2'297'945  3.06541e6 
Philadelphia  13'389  40'003  1'151'166  1.65428e7 
The problems ndo22 and ndo148 are relatively small problems, but they are known to be difficult and have served as test for various method. The problem 904 is based on real telecommunications networks.
# Nodes  # Arcs  # Comm.  Best Value  
ndo 22  14  22  23  1.88237e3 
ndo 148  158  148  122  1.39500e5 
904  106  904  11130  1.37850e7 
Bibliography
[BdMV04] F.Babonneau, O. du Merle and J.P. Vial. Solving large scale linear multicommodity flow problems with an active set strategy and ProximalACCPM. to appear in Operations Research, 2005.
[LY04] T. Larsson and Di Yuan. An Augmented Lagrangian Algorithm for Large Scale Multicommodity Routing. Computational Optimization and Applications. 2004, vol 27(2), p187215.