This page provides a collection of instances and random generators of Multicommodity Flow problems of various types:

Linear Multicommodity Flow problems, ordinary LPs but challenging due to their size;

NonLinear Multicommodity Flow problems, difficult both for their size and the nonlinearity of the objective function;

Multicommodity Network Design problems, difficult mainly both for the presence of integer variables (although the continuos relaxation can be challenging for their size, too);

Unsplittable Multicommodity Network Flow problems, where each commodity is an Origin/Destination pair and the flow has to travel along a unique path (which is the case of many protocols in telecommunication networks), difficult because flow variables are integer;

Unsplittable Multicommodity Network Design, particularly difficult because

*both*flow and design variabless are integer;

We also provide some supporting material:

Some links to similar pages around the web;

A small bibliography of the articles where the instances have been tested.

A service C++ class for (MMCF)-solvers, Graph. 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.

All instances are packed with "tar" and compressed with "gzip"; these are
ubiquitous on unix systems, and available
for essentially every other architecture. Once a file *f*.tar.gz has been
downloaded, it must be first decompressed (gzip -d *f*.tar.gz under unix)
and then un-tarred (tar xvf *f*.tar under unix) to retrieve the original
files and/or directories. Files of the type *f*.tgz are compressed by the
tar command, and can be decompressed and un-tarred at the same time
(tar xzvf *f*.tgz).

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.

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.

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 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.

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.".

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).

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.

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 (for today's
standards, rather 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 the instances have been
"inverted" w.r.t. the ones found in the
original distribution, i.e., origins have been transformed into
destinations and vice-versa and arcs have been changed orientation, so that
one can test both with instances where commodities have a common
*origin* and with equivalent instances where commodities have a
common *destination*.

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.

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.

Then, you will need a single-commodity (MCF) generator to produce the
"basic" instances; you can find several of them here.
For two of them (GridGen and
RmfGen) we provide input and batch files
for generating both the single-commodity and the Multicommodity instances.
After that the generator has 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 (old) results for 4 solution
approaches from
here.

Other feasible generators are available at the Dimacs site.

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").

These are three different groups of randomly generated instances on
*undirected* graphs provided by *Pamela Vance*; the generators are
not available.

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.

These 8 instances (267k) are intended to
simulate the data of a real-world aerline transportation problem: they have
been provided by *Stefan Eger*.

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:

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 |

These two sets of test problems, planar networks and grid networks, originate from the paper [LY04]. Commodities are pairs of Origin and Destination nodes in these two problem sets.

For the set of planar networks, nodes are randomly chosen as points in the
plane, and arcs link neighbour nodes in such a way that the resulting graph
is planar. The origin and destination nodes are randomly chosen among the
node set. Arc costs are euclidean distances, while demands and capacities
are uniformly distributed in given intervals. There are
10 instances(760k). The planar*n* files
contains an instance with *n* nodes, *n* going from 30 to 2500.
The format.doc text file describes of the format of the instances.

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.

Since the format of those instances is among those that are read by
Graph, *Tiziano Parriani* has developed the
ly2mnet translator which produces instances
in the Mnetgen format out of these in the
original format. Hence we can now distribute the
translated planar instances (1.6M) and
the translated grid instances(1.1M).

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.

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].

Note that the format of those instances is *not* among those that are
read by Graph. Anybody willing to provide a translator?

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.

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) (see e.g. [FrGo13]).

This is a group of 196 instances, divided in three classes, used in [CFG01] and subsequent papers. The format of the instances is:

- number_of_nodes number_of_arcs number_of_commodities
- for each arc:

from_node to_node variable_cost capacity fixed_cost any_number any_number - for each commodity:

from_node to_node demand (>0)

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.

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 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 are available in the file
R.tgz (156K). They have a naming scheme
r*x*.*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).

The Canad problems are a group of 96 randmoly generated instances of the
*Fixed Charge* (MMCF).

They are generated with two distinct random generators, "Bipart" and
"Mulgen", that have been developed by *Bernard Gendron*. The first
generator produces Multicommodity capacitated transportation instances (on
bipartite graphs); the second produces instances on generic graphs, either
with a single source/sink pair for each commodity or with multiple
source/sink pairs for each commodity.

To use the generators, get the file Canad.tgz: 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 *s*
format parameter in the "file constructor").

A set of 48 "large" problems (up to 800 commodities, 50 nodes and 1200 arcs)
has been generated to test more advanced decomposition approaches in [FrGo13].
They can be obtained either downloading the (largish) file
CanadN.tgz (42M), or compiling the *Mulgen*
generator and running it with the parameter files from
CanadN-p.tgz (1.5k).

The first version of the generator used to produce the Bipart and Mulgen
relied on a home-made random numbers generator that has shown to have
portability problems. The generator has been improved, but as a consequence
the current versions of Bipart and Mulgen do not produce any longer the
instances they used to. Therefore, the instances produced by the *old*
version of the generator are available to be dowloaded here.

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.

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.

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.

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.

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.

Here is the list of all the groups of Unsplittable Multicommodity Network Flow instances and random generators available from this site:

Note that some Linear Multicommodity Flow problems have the Origin/Destination structure (and no individual capacities over arcs) so that they can be used as instances of (UMMCF), but this section contains instances specifically developed for (UMMCF). Conversely, any (UMMCF) instance can be considered as a Linear (MMCF) one by just dropping the integrality constraints on the flow variables.

These instances use either real-world telecommunication network topologies
or realistic ones (as far as telecommunication networks go) and process them
through the FNSS tool to produce realistic
capacities and demands (again, as far as telecommunication networks go).

Once the topology is loaded in FNSS (either by reading a gml file or by its
internal random generator), one can assign realistic link capacities using
one of the three allocation algorithms specifically designed for modeling
PoP-level link capacity assignment in ISP backbones. These algorithms exploit
the correlation between the amount of capacity assigned to a specific link
and three metrics that are meant to capture the importance of the link; in
particular, we used the *edge betweenness centrality* metric, that
corresponds to the number of shortest paths passing through a specific link.
We specified a set of possible link capacity values (1, 10, and 40 Gbps),
and a capacity is assigned from the set to all the links of the network
proportionally to the edge betweenness centrality.

After this is done, realistic traffic matrices are generated that take into
account the capacities of the network. To generate a traffic matrix one
needs to specify the mean traffic demand (0.8 Gbps) standard deviation
(0.05).

The resulting instances are generated in an XML format for which we have
developed a translator into the
Mnetgen format. Some different sets of
instances are available which mostly differ from how the initial topology
is generated.

These are (just two) random instances generated directly by FNSS using the waxman-1 model with the following parameter configuration:

number of nodes = | 100, 200 |
---|---|

alpha = | 0.4 (arc-density) |

beta = | 0.1 (FNSS default) |

L = | 1 (FNSS default) |

As far as these instances go they are quite largish, although one could
generate much larger ones. Note that FNSS generates all possible
*n*^{2} commodities corresponding to all
possible Origin-Destination pairs, that can be quite too many when
*n* is large; therefore, during the Mnetgen translation the number of
commodities was reduced to *n* log( *n* ).

This data set, provided by *Aristide Mingozzi*, is formed of thw
groups of five instances each, on graphs with 30 nodes and several 100s
arcs. It can be downloaded here and
comprises a "format.txt" file describing the format of the instances,
which have been used in [BM09].

Some other collections of multicommodity-related instances can be found at the following places:

A collection of

*Fixed Charge*(MMCF) instances are distributed by*Kay Holmberg*, and used in [HY00].A collection of

*Network Design*(MMCF) instances of various types are distributed by*Alper Atamturk*, and used in [At02, AR02].The SNDlib library of Survivable Network Design instances from

*ZIB*, described in [OPTW10].The GARR network.

[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

[BM09] E. Bartolini, A. Mingozzi "Algorithms for the non-bifurcated
network design problem" *Journal of Heuristics* **15** (2009),
259-281

[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, Università 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

[FrGo13] A. Frangioni, E. Gorgone
"Generalized
Bundle Methods for Sum-Functions with ``Easy'' Components: Applications to
Multicommodity Network Design" *Mathematical Programming*, to appear,
2013

[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 Augmente 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

[OPTW10] S. Orlowski, M. Pioro, A. Tomaszewski, and R. Wessaly
"SNDlib 1.0 - Survivable Network Design Library" *Networks*
**55**(3) (2010), 276-286

[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