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 Sioux-Falls, 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 |
|
| Sioux-Falls | 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 Proximal-ACCPM. 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), p187-215.