cherubino

Multicommodity Flow Problems

Last update: 02/11/2021 (the original page has been moved to the CommaLAB web site, although a redirect has been kept)

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

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.
  • The MMCFBlock component of the SMS++ project that allows to read an (MMCF) instance from file(s) in most of the formats used in this page and store it in memory (actually in two different ways, the flow formulation and the knapsack formulation, but nonetheless) in such a way that a Solver (be it a general-purpose one or a specialised one) can read it independently from the original format.

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.

Linear Multicommodity Flow Problems

Here is the list of all the groups of Linear Multicommodity Min-Cost Flow (MMCF) instances/generators available from this site.

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 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 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. Refer 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 MMCFBlock (the m format parameter in the load( name , format ) method).

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

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 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 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 ready-to-download instances up to PDS100. Due to a specific request we even add PDS 50 to 100 instances in MPS format.

pds2mngn.C is a little translator that transform the PDS instances in the Mnetgen format, that is read by MMCFBlock (the m format parameter in the load( name , format ) method).

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 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 (for today’s standards, rather small) instances in JL format, that is read by MMCFBlock (the p, o, d or u format parameters in the load( name , format ) method). 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 contains the directory JLF containing the subdirectories ALK, Assad, Chen.DSP, Chem.PSP, Farvolden and Powell. Each directory contains the instances.

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. 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; 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 MMCFBlock (the c format parameter in the load( name , format ) method). For RmfGen, the directory Results contains the (old) results for 4 solution approaches from here.

Other feasible generators are available at the Dimacs site.

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 are in PPRN format, that is read by MMCFBlock (the c format parameter in the load( name , format ) method).

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 file vance.tar.gz 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 MMCFBlock (the O format parameter in the load( name , format ) method; 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 AerTranspo problems

These 8 instances 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 MMCFBlock (the o format parameter in the load( name , format ) method).

The following table lists the size of the instances:

k1840132140138166189194
n2349141147158188207209
m71137449520477673726765

The Planar and Grid problems

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 planarn 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, 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 and the translated grid instances.

The Jump problems

This is a set of 11 instances 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 MMCFBlock. Anybody willing to provide a translator or to develop a specific Block?

At some not-well-defined point in time, the original file got lost somehow and we were unable to recover it, so it appears this data set is lost.

NonLinear Multicommodity Flow Problems

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

The genflot generator 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 MMCFBlock. Anybody willing to provide a translator or to develop a specific Block?

The 3DTables generator

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.

Also this file seems to have mysteriously disappeared at some point and is no longer available.

Multicommodity Network Design Problems

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

These have been used to produce benchmark instances for several papers (e.g., [CFG01, FGG17, FGG18, KBCFGG21]). Some of these problems can be interesting even from the viewpoint of those interested in solving the Linear (MMCF) (see e.g. [FrGo13]).

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:

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

namenodesarcscommoditiesF/VT/L
c332023040VL
c352023040VT
c362023040FT
c3720230200VL
c3820230200FL
c3920230200VT
c4020230200FT
c412030040VL
c422030040FL
c432030040VT
c442030040FT
c4520300200VL
c4620300200FL
c4720300200VT
c4820300200FT
c4930520100VL
c5030520100FL
c5130520100VT
c5230520100FT
c5330520400VL
c5430520400FL
c5530520400VT
c5630520400FT
c5730700100VL
c5830700100FL
c5930700100VT
c6030700100FT
c6130700400VL
c6230700400FL
c6330700400VT
c6430700400FT

The C+ instances

The C+ instances are available in the file CPlus.tgz. 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. They have a naming scheme rx.y, where x and y have the following meaning:

xnodesarcscommodities
01103510
01103525
03103550
04106010
05106025
06106050
07108210
08108325
09108350
102012040
1120120100
1220120200
132022040
1420220100
1520220200
162031440
1720318100
1820315200
yfixed costcapacity
111
251
3101
412
552
6102
718
858
9108

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 Bipart and Mulgen problems

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

The Large Mulgen problems

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, or compiling the Mulgen generator and running it with the parameter files from CanadN-p.tgz.

The “old” Bipart and Mulgen problems

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 in three separate groups: Bipart, Mulgen I and Mulgen II.

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

This group of 9 instances 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.

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.

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

Unsplittable Multicommodity Network Flow Problems

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.

The FNSS problems

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.

The GARR instances

These 10 instances corresponding to the Italian academic network (at various stages of development) have been downloaded (as far as the topology go) from the Internet Topology Zoo (see the links section).

The SNDLib instances

These 23 instances have been downloaded (as far as the topology go) from the SNDlib library (see the links section). Note that SNDLib also provide link capacity and (multiple) traffic matrices, but for the sake of uniformity we used randomly-generated data.

The Waxman instances

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

number of nodes100, 200
alpha0.4 (arc-density)
beta0.1 (FNSS default)
L1 (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 n2 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 ).

Unsplittable Multicommodity Network Design Problems

The Mingozzi problems

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:

Bibliography

[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

[FGG17] A. Frangioni, B. Gendron, E. Gorgone “On the Computational Efficiency of Subgradient Methods: a Case Study with Lagrangian Bounds” Mathematical Programming Computation 9(4), 573–604, 2017

[FGG18] A. Frangioni, B. Gendron, E. Gorgone “Dynamic Smoothness Parameter for Fast Gradient Methods” Optimization Letters 12(1), 43–53, 2018

[FrGo13] A. Frangioni, E. Gorgone “Generalized Bundle Methods for Sum-Functions with “Easy” Components: Applications to Multicommodity Network Design”Mathematical Programming145(1), 133–161, 2014

[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

[KBCFGG21] M.R.A. Kazemzadeh, T. Bektas, T.G. Crainic, A. Frangioni, B. Gendron, E. Gorgone “Node-Based Lagrangian Relaxations for Multicommodity Capacitated Fixed-Charge Network Design”Discrete Applied Mathematics, to appear, 2021

[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