This page provides a collection of instances and random generators of Multicommodity Flow problems. The page comprises:
A service C++ class for (MMCF)-solvers, Graph, is also available on this site; it allows to read an (MMCF) instance from file(s) in most of the formats used in this page and store it in memory in an unique format, so that the solver can read it independently from the original format. It offers various nice features, like pre-processing and output in MPS format (readable by all LP solvers). Description of the formats is also available with the class.
This site is thought as a service to the optimization community; if you have any instance/generator to add, or a suggestion for a page to link, please contact us.
Here is the list of all the groups of Linear Multicommodity Min-Cost Flow
(MMCF) instances/generators available from this site.
However, the generator has been re-coded in C++, and slightly enhanced, by
Antonio Frangioni: this new version and input files for a new group
of 366 instances developed by Paola Cappanera, and tested in [CF03],
are available here. The new set of input files has been developed because
the old Mnetgen instances are believed to be "too easy" [KDM96, SM91]: it
has been reported that the solution times with different solution
approaches tend to decrease as the size increase. This is not the case of
the new group [FG99, CF03].
The file Mnetgen.tgz (28k) contains a
directory Mnetgen containing a lot of subdirectories named
pr{n}.{k}, a directory Result and the files batch, makefile
and mnetgen.C. Simply type "make" to build the executable, then execute the
batch to create the first 216 instances. Refere to the file "batch" for
creating the additional 150 larger instances: be careful, though, since the
first 216 already require considerable disk space.
The format of the files produced by Mnetgen is described in mnetgen.C. This
format is read by Graph (the m format parameter in the "file
constructor").
In the directory Results, the running times and optimal solution values for
6 different solution algorithms (Cplex, IPCplex, IPM, LOQO, MMCFB and PPRN)
are reported for all the first 216 instances, lexicographically ordered
(in the same order in which they are created by the file batch); the results
are taken from [FG99].
Update 8/6/2006: A small bug in Mnetgen has been corrected which
produced segfaults with some input files. Thanks to Dae-Sik Choi
from University of Corea for the fix.
The file Pds.tar.gz (168k) contains the directory
Pds containing the subdirectories gen and Results and the files makefile and
pds2mngn.C. The directory gen contains the actual generator (essentially
identical to the
standard distribution). The generator is notoriously buggy: in fact,
Jordi Castro has produced a new version of
the sortc9.f file (4814 bytes) that seems to solve the problem. He reports
that "the ``only'' problem when generating the PDS tests is that two arrays
are no initialized to 0 in the file sortc9.f. So if the compiler does it, the
PDS generator works fine, otherwise it doesn't. [...] I have included the new
sortc9.f (more portable) including the initialization of these arrays.".
pds2mngn.C is a little translator that transform the PDS instances in the
Mnetgen format, that is read by Graph (the
m format parameter in the "file constructor"). The file is commented,
and the makefile is ready for the use.
In the directory Results, the running times and optimal solution values for
6 different solution algorithms (Cplex, IPCplex, IPM, LOQO, MMCFB and PPRN,
taken from [FG99]) are reported for the first 24 PDS instances.
The file JLF.tgz (1506k) contains the directory
JLF containing the subdirectories ALK, Assad, Chen.DSP, Chem.PSP, Farvolden and
Powell. Each directory contains the instances.
To use dimacs2pprn, get the file dmx2pprn.tgz: it
contains a directory dmx2pprn containing the files Format (which describes the
PPRN format), dmx2pprn.C, imakefile, fmakefile and OPTtypes.h. It is possible to
guarantee that the generated instances have a feasible solution (refere to
dimacs2pprn.C for details); however, any (MCF)
solver using the MCFClass interface is required for this.
Then, you will need a single-commodity (MCF) generator to produce the "basic"
instances: here, five such generators are provided, i.e.
GridGraph,
Netgen,
Grid-On-Torus,
GridGen and
RmfGen. For the last two ones, other
than the generators we provide input and batch files for generating both the
single-commodity and the Multicommodity instances. After that the generator
have been compiled, the batch "sbatch" produces the single-commodity ones, so
that executing the batch "mbatch" the Multicommodity ones are generated. These
files are in PPRN format, that is read by Graph (the c format parameter
in the "file constructor"). For RmfGen, the directory Results contains the
results for 4 solution approaches, as explained
here.
Other feasible generators are available at the
Dimacs site.
The file vance.tar.gz (152k) contains the
directory vance containing the subdirectories p, q, r10 and Results and the
file cyn2jlf.C. The directories p and q contain respectively 6 and 12 small
and easy instances, while the directory r10 contains 12 instances, 10 of
which (i.e. all but r10 and r10.1) are considerably harder. The instances
r10-5-x have almost integral data, while the r10-55-x have "highly fractional"
data; even though for the rest the instances are similar, this can have an
impact on the solution times of some codes, as demonstrated by the results
reported in Results/log.r10.
cyn2jlf.C is a little translator that turns the instances from their original
format to the JL Origin-Specific Problem format in
which the instances are provided. This format is read by Graph (the O
format parameter in the "file constructor"; note the capital `O',
corresponding to a problem on an undirected graph). The original distribution
can be found at
Pamela Vance's
ftp site.
The instances range from small to quite large, even though not enormous: they
are interesting since they have a relatively large number of commodities,
close to the number of nodes. Here, a commodity is the flow out of a given
source node, i.e. a tree; in fact the instances are in
JL Origin-Specific Problem format, that is read
by Graph (the o format parameter in the "file constructor").
The following table lists the size of the instances:
Linear Multicommodity Flow Problems
The Mnetgen generator(s)
Mnetgen is the most famous (and probably the first) random generator of
Multicommodity Min Cost Flow instances: the
original Mnetgen [AK77] and input files (15k) for a "standard" set of 120
instances are kept here for completeness, although their standard distribution
is rather
this one.The PDS problems
The PDS problems are probably the most famous group of (MMCF) instances, and
have been used by several researchers
[Ca00, CN96, FG99, GK95, McB98, PZ92, SM91] to test their codes. These
instances come from a model of transportation of patiens away from a place of
military conflict: all the instances represent the same scenario, but the
model is parametric with respect to the planning horizont t (the number
of days covered by the model), increasing which larger and larger instances
are generated. The instances have a space-time network whose size
increases about linearly with t: however, the number of commodities is
always 11. The PDS instances are generally believed to be "hard": in fact,
about 30% of arcs have a tight mutual capacity constraint at optimality.
In any event, we also provide files with ready-to-download instances up to
PDS100:
PDS1 .. PDS9 (640k),
PDS10 .. PDS15 + PDS18 (1480k),
PDS{20, 21, 24, 27} (1582k),
PDS{30, 33, 36, 40} (2278k),
PDS50 (1001k),
PDS60 (1219k),
PDS70 (1414k),
PDS80 (1589k),
PDS90 (1751k) and
PDS100 (1909k). The JLF problems
These instances have been collected by Kimberly L. Jones, Irv
Lustig and Judith Farwolden [JLFP93] for testing a computational
approach to (MMCF). This test contains 6 small groups of (usually small)
instances in
JL format, that is read by Graph (the p,
o, d or u format parameters in the "file constructor").
Most instances have the Origin-Destination Formulation, hence they have both a
".sup" file for the Product-Specific (aggregated) Formulation and a ".od" file
for the OS (disaggregated) formulation. Note that, for technical reasons, the
instances have been "inverted" w.r.t. the original ones in such a way that
commodities have a common origin rather than a common destination
as in the
original distribution.The dimacs2pprn "meta" generator
dimacs2pprn is a "meta" generator of (MMCF), originally developed by Jordi
Castro [Ca00, CN96] and later polished and enhanced by Antonio
Frangioni. It takes the description of a single-commodity Min Cost
Flow instance in
Dimacs
standard format and turns it into a (MMCF) instance by essentially
constructing k copies with deficits and capacities "scaled" of a random
quantity and randomly twisted costs. It is a "meta" generator because the
structure of the resulting instances depends on that of the original
single-commodity ones, rather than being "hard wired" into the generator,
like Mnetgen or
Bipart and Mulgen.The hydrothermal problems
This is a group of 5 medium-to small instances provided by Jordi Castro,
who has in turn received them by Narcis Nabona [CN96]. In his own
words: ".. These appear in the field of hydrothermal energy generation. These
test cases are obtained through a sophisticated process which reads some data
about a system of reservoirs. These programs are not mine: they belong to the
Nonlinear Optimization Group of the Universitat Politecnica de Catalunya
(Barcelona)... Of course the hydrothermals problems are not really large, but
they have the added value of being real-case networks (though the objective
function is not a real one, it is just a linear approximation)." The
hydrothermal instances (28k) are in
PPRN format, that is read by Graph (the c
format parameter in the "file constructor").The Vance problems
These are three different groups of randomly generated instances on
undirected graphs provided by Pamela Vance; the generators are
not available.The AerTranspo problems
These 8 instances (267k) are intended to
simulate the data of a real-world aerline transportation problem: they have
been provided by Stefan Eger.
| k | 18 | 40 | 132 | 140 | 138 | 166 | 189 | 194 |
|---|---|---|---|---|---|---|---|---|
| n | 23 | 49 | 141 | 147 | 158 | 188 | 207 | 209 |
| m | 71 | 137 | 449 | 520 | 477 | 673 | 726 | 765 |
The regular structure of grid networks make it easier to make comparisons between various solutions methods. Note that there is usually a large number of paths between two nodes in a grid network, this may make solution methods based on path generation less efficient for this problem set. The set contains 15 instances(672k), with the number of nodes ranging between 25 and 1225. The nodes are organized as a regular grid. Thus there are four incoming and four outgoing arcs for every internal node of the grid. The arc costs, commodities, and demands are generated similar to that of planar networks. The format.doc text file describes of the format of the instances.
Note that the format of those instances is not among those that are read by Graph. Anybody willing to provide a translator?
The Jump problems
This is a set of 11 instances (144k) of (MMCF)
with "jump constraints", that is, a variant of (MMCF) when flow from any
source cannot traverse more than a fixed number k of arcs before
getting to the destination. This is a frequent constraint in
telecommunications, and in fact the provided instances have very many
commodities. They have been used in [MV97] to test a basis-partitioning
approach for the problem; of course, they can be taken as ordinary (MMCF)
instances by disregarding the jump constraint (specified by just the number
k). The format of these instances is described in the included
"format" file, and it is not among those that are read by Graph.
Anybody willing to provide a translator?
Here is the list of all the groups of NonLinear Multicommodity Min-Cost
Flow (NL-MMCF) instances/generators available from this site.
Note that the format of those instances is not among those that are
read by Graph. Anybody willing to provide a translator?
Here is the list of all the groups of Multicommodity Network Design instances
and random generators available from this site
Some of these problems can be interesting even from the viewpoint of those
interested in solving the Linear (MMCF).
The basic elements characterizing each C and C+ instance are: number of nodes,
number of arcs, number of commodities. It is also important to know
whether the fixed costs are predominat relatively to the variables costs or vice-versa,
and whether the capacities are loose or tight.
The C instances
The C instances are available in the file C.tgz (168K).
The following the table maps each instance name into its characteristics; in
particular, F means that the fixed costs are predominat relatively to the
variables costs and V means the converse, while L means that the
capacities are loose while T means that the capacities are tight.
NonLinear Multicommodity Flow Problems
The genflot generator
The genflot generator (5k) has been
developed by Robert Sarkissian and used for testing a decomposition
approach to (NL-MMCF) [GGSV96]. A README file is provided with the
distribution which describes the details of the functionality and input /
output format of the generator. Also, a "batch" file is provided containing
the parameters for generating the 22 small-to-very large instances used in
[GGSV96].The 3DTables generator(s)
The 3Dtables generator produces convex
quadratic separable multicommodity flow instances coming from a problem of
statistical data protection. These instances are used in [Ca05] and they
provide saturated multicommodity problems, i.e., all mutual arc capacities
are active; this makes them difficult to solve with some algorithmic
approaches. The generator produces instances in
PPRN format.
The NDO problems
This is a set of two (quite small) problems,
provided by Frederic Babonneau and used in [GGSV96]. The file data format is
explained in the included file format.doc.
Multicommodity Network Design Problems
The Canad problems
The Canad problems are several groups of randmoly generated instances of the
Fixed Charge (MMCF), developed by Bernard Gendron and used in
several pubblications to test relaxations and exact or heuristic approaches to
the problem.
The C, C+ and R problems
This is a group of 196 instances, divided in three classes, used in [CFG01] and
subsequent papers. The format of the instances is:
from_node to_node variable_cost capacity fixed_cost any_number any_number
from_node to_node demand (>0)
| name | nodes | arcs | commodities | F/V | T/L |
|---|---|---|---|---|---|
| c33 | 20 | 230 | 40 | V | L |
| c35 | 20 | 230 | 40 | V | T |
| c36 | 20 | 230 | 40 | F | T |
| c37 | 20 | 230 | 200 | V | L |
| c38 | 20 | 230 | 200 | F | L |
| c39 | 20 | 230 | 200 | V | T |
| c40 | 20 | 230 | 200 | F | T |
| c41 | 20 | 300 | 40 | V | L |
| c42 | 20 | 300 | 40 | F | L |
| c43 | 20 | 300 | 40 | V | T |
| c44 | 20 | 300 | 40 | F | T |
| c45 | 20 | 300 | 200 | V | L |
| c46 | 20 | 300 | 200 | F | L |
| c47 | 20 | 300 | 200 | V | T |
| c48 | 20 | 300 | 200 | F | T |
| c49 | 30 | 520 | 100 | V | L |
| c50 | 30 | 520 | 100 | F | L |
| c51 | 30 | 520 | 100 | V | T |
| c52 | 30 | 520 | 100 | F | T |
| c53 | 30 | 520 | 400 | V | L |
| c54 | 30 | 520 | 400 | F | L |
| c55 | 30 | 520 | 400 | V | T |
| c56 | 30 | 520 | 400 | F | T |
| c57 | 30 | 700 | 100 | V | L |
| c58 | 30 | 700 | 100 | F | L |
| c59 | 30 | 700 | 100 | V | T |
| c60 | 30 | 700 | 100 | F | T |
| c61 | 30 | 700 | 400 | V | L |
| c62 | 30 | 700 | 400 | F | L |
| c63 | 30 | 700 | 400 | V | T |
| c64 | 30 | 700 | 400 | F | T |
The C+ instances
The C+ instances are available in the file CPlus.tgz (32K). They are similar to the C instances, with a set of different sizes. The characteristics of each instance can be told by the file name, with the above naming scheme.
The R instances
The R instances are available in the file R.tgz (156K). They have a naming scheme rx.y, where x and y have the following meaning:
| x | nodes | arcs | commodities |
|---|---|---|---|
| 01 | 10 | 35 | 10 |
| 01 | 10 | 35 | 25 |
| 03 | 10 | 35 | 50 |
| 04 | 10 | 60 | 10 |
| 05 | 10 | 60 | 25 |
| 06 | 10 | 60 | 50 |
| 07 | 10 | 82 | 10 |
| 08 | 10 | 83 | 25 |
| 09 | 10 | 83 | 50 |
| 10 | 20 | 120 | 40 |
| 11 | 20 | 120 | 100 |
| 12 | 20 | 120 | 200 |
| 13 | 20 | 220 | 40 |
| 14 | 20 | 220 | 100 |
| 15 | 20 | 220 | 200 |
| 16 | 20 | 314 | 40 |
| 17 | 20 | 318 | 100 |
| 18 | 20 | 315 | 200 |
| y | fixed cost | capacity |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 5 | 1 |
| 3 | 10 | 1 |
| 4 | 1 | 2 |
| 5 | 5 | 2 |
| 6 | 10 | 2 |
| 7 | 1 | 8 |
| 8 | 5 | 8 |
| 9 | 10 | 8 |
The larger the fixed cost, the more the fixed costs are important relatively to the variable costs (see F/V in the C and C+ instances). The larger the capacity, the more the capacity constraints are tight (see T/L in the C and C+ instances).
To use the generators, get the file Canad.tar.gz (18K): it contains a directory Canad containing the three subdirectories Bipart, Data and Mulgen and the file Format. The latter describes the format of the files produced by the generators.
Bipart and Mulgen contain the source code for the generators. In each directory there is a makefile ready for the use, so that just typing "make" should be enough to build the executables. Then, in each directory there is a file "batch" that generates the instances (32 with Bipart and 64 with Mulgen), using the parameters found in the subdirectory Data. These instances are in the "Canadian" format, that is read by Graph (the c format parameter in the "file constructor").
| Bipart | Mulgen I | Mulgen II |
|---|---|---|
| 1 - 8 (.6Mb) | 33 - 40 (.6Mb) | 65 - 72 (.8Mb) |
| 9 - 16 (1Mb) | 41 - 48 (.8Mb) | 73 - 80 (.9Mb) |
| 17 - 24 (2.1Mb) | 49 - 56 (3.1Mb) | 81 - 88 (3.6Mb) |
| 25 - 32 (3.6Mb) | 57 - 64 (4.1Mb) | 89 - 96 (4.9Mb) |
For these old 96 instances, considered as (MMCF)s (i.e. disregarding the Fixed Charge costs), running times and optimal solution values for 6 different algorithms (Cplex, IPCplex, IPM, LOQO, MMCFB and PPRN) are available.
This group of 9 instances (8k) have been
provided by Christelle Wynants: instances 1 - 4 are based on a
real-world network but the demands are randomly generated, while instances
5 - 9 are completely randomly generated. The file format.txt describes the
format of the instances.
These instances (30k) are fairly small in
terms of underlying graph (12 to 21 nodes, 22 to 51 arcs), yet rather difficult
to solve; at least for the first two groups, this is also due to a fully dense
traffic matrix, hence a large number of commodities. The first set represents
a Network Design problem relative to an ATM network in Los Angeles, the second
a telecommunication network in the greater New York area, and the third a
backbone network in Norway. A readme file is provided which explains the
format of the files. The original distribution of the instances can be found
here.
Some other collections of multicommodity-related instances can be found
at the following places:
[AK77] A. Ali, J.L. Kennington "Mnetgen program documentation"
Technical Report 77003 (1977), Dept. of Ind. Eng. and
Operations Research, Southern Methodist University, Dallas
[At02] A. Atamturk "On capacitated network design cut-set polyhedra"
Mathematical Programming 92 (2002), 425-437
[AR02] A. Atamturk, D. Rajan "On splittable and unsplittable flow
capacitated network design arc-set polyhedra" Mathematical
Programming 92 (2002), 313-333
[CF03] P. Cappanera, A. Frangioni "Symmetric and Asymmetric
Parallelization of a Cost-Decomposition Algorithm for Multi-Commodity
Flow Problems" INFORMS Journal On Computing 15(4) (2003),
369-384
[Ca00] J. Castro "A specialized interior-point algorithm for multicommodity
network flows" SIAM Journal on Optimization 10(3) (2000),
852-877
[Ca05] J. Castro "Quadratic interior-point methods in statistical
disclosure control" Computational Management Science, to appear
(2005)
[CN96] J. Castro, N. Nabona "An Implementation of Linear and Nonlinear
Multicommodity Network Flows" EJOR 92 (1996), 37-53
[CD04] A. Chabrier, E. Danna, C. LePape and L. Perron "Solving a
Network Design Problem" Annals of Operations Research 130
(2004), 217-239
[CFG01] T.G. Crainic, A. Frangioni, B. Gendron "Bundle-Based Relaxation
Methods for Multicommodity Capacitated Fixed Charge Network Design
Problems" Discrete Applied Mathematics 112 (2001), 73-99
[Fr97] A. Frangioni "Dual Ascent Methods and Multicommodity Flow Problems"
Ph.D. Dissertation TD 5/97 (1997), Dip. di Informatica,
Univ. di Pisa
[FG99] A. Frangioni, G. Gallo "A bundle type dual-ascent approach to
linear multicommodity min cost flow problems"
INFORMS Journal on Computing 11(4) (1999), 370-393
[GGSV96] J.-L. Goffin, J. Gondzio, R. Sarkissian, J.-P. Vial "Solving
nonlinear multicommodity flow problems by the analytic center cutting
plane method" Mathematical Programming 76 (1996),
131-154
[GK95] M.D. Grigoriadis, L.G. Kahchyan "An Exponential-Function Reduction
Method for Block-Angular Convex Programs" Networks 26 (1995),
59-68
[Gu99] O. Gunluk "A Branch-and-Cut Algorithm for Capacitated Network Design
Problems" Mathematical Programming 86 (1999), 17-39
[HY00] K. Holmberg, D. Yuan "A Lagrangian heuristic based branch-and-bound
for the capacitated network design problem" Operations Research
48 (2000), 461-481
[LY04] T. Larsson, D. Yuan "An Augmented Lagrangean Algorithm for Large
Scale Multicommodity Routing" Computational Optimization and
Applications 27(2) (2004), 187-215
[JLFP93] K.L. Jones, I.J. Lustig, J.M. Farwolden, W.B. Powell,
"Multicommodity Network Flows: The Impact of Formulation on
Decomposition" Mathematical Programming 62 (1993),
95-117
[LSSW99] M. Labbé, R. Seguin, P. Soriano, C. Wynants "Network
Synthesis with Non-Simultaneous Multicommodity Flow Requirements:
Bounds and Heuristics" Tech. Report 99/26 (1999), S.M.G.,
Univeristé Libre de Bruxelles
[KDM96] S. Kontogiorgis, R. De Leone, R.R. Meyer "Alternating directions
splitting for block angular parallel optimization"
JOTA 90(1) (1996), 1-29
[MV97] J.-F. Maurras, Yann Vaxès "Multicommodity network flow
with jump constraints" Discrete Mathematics 166(15) (1997),
481-486
[McB98] R.D. McBride "Advances in Solving the Multicommodity Flow Problem"
SIAM Journal on Optimization 8(4) (1998), 947-955
[PZ92] M.C. Pinar, S.A. Zenios, S.A. "Parallel decomposition of
multicommodity network flows using a linear-quadratic penalty algorithm"
ORSA Journal on Computing 4 (1992), 235-249
[SM91] G. Schultz, R. Meyer "An interior-point method for block-angular
optimization" SIAM Journal on Optimization 1 (1991),
583-682
The Reserve problems
The Reserve problem in telecommunications [Fr97, LSSW99] asks for optimally
sizing reserve capacities on the arcs of an existing telecommunication
network to face one-arc "catastrophic" failures; the model can then be
complicated to allow multiple-arc failures and node failures. Formulated as
an ILP, the Reserve problem is essentially an (Integer) Nonsimultaneous
(MMCF) where the commodities are divided in groups, and only the commodities
within the same group compete for the arc mutual capacities.The Gunluk problems
This data set, provided by Oktay Gunluk, is formed of three groups of
instances of the Capacity Expansion Problem, a Multicommodity Network Design
problem where the capacity of an existing telecommunication network must be
increased with the objective of minimizing both the cost of the newly
installed capacity and the resulting routing costs. The new capacity can be
installed by means of two different types of facilities, with
different costs: multiple copies of each facility can be installed
on each arc, and the capacity provided by each "large" facility is
a multiple of the capacity provided by each "small" facility.Useful links
Bibliography