This page provides a collection of instances and random generators of Single-commodity Min-Cost Flow problems of various types:

Linear cost problems, ordinary LPs with possibly the most elegant and algorithmically exploitable matrix structure;

Single-commodity NonLinear Network Design problems, more difficult due to both the presence of integer variables relative to "constructing" arcs/nodes of the graph and to the nonlinearity of the objective function.

We also provide a small bibliography of some articles where the instances have been tested.

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.

Several well-known random generators of Min-Cost Flow problems have been developed over the years to test the several available specialized solvers for the problem; see e.g. the Dimacs site.

Here we distribute six ones of them, all producing instances in the Dimacs standard format: Complete, GridGraph, Netgen, Grid-On-Torus, GridGen and RmfGen. The first one generates complete graphs, the other graphs with either random or some sort of grid structure. For each generator we include batches and/or parameter files to produce the instances that have been used in different articles to test either algorithms for the problem at hand [DAFSS10, FrGe04, FrGe07a, FrGe07b] or algorithms for Multicommodity Min-Cost Flow problems [CaFr03, Fr97, FrGa99] (in this case, the single-commodity instances are typically used as the "basis" to construct a multicommodity one).

We distribute three groups of randomly-generated (Convex) Quadratic-cost Network Design problems used in [FGGP11] to test solution approaches based on the "Perspective Reformulation". These are instances with 1000 nodes (1.7Mb), 2000 nodes (3.2Mb), and 3000 nodes (4.8Mb). We also distribute the three-pass random generator used to produce them; it uses netgen to construct the "basic" single-commodity, linear cost instance upon which fixed and quadratic costs are subsequently added (see the cited references and the readme file in the generator for details).

[CaFr03] 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

[DAFSS10] P. Dell'Acqua, A. Frangioni, S. Serra Capizzano
"Multi-iterative Techniques of Multigrid Type for Solving Large Linear
Systems with Structure of Graph" *Technical Report* **10-02**,
Dipartimento di Informatica, Università di Pisa, 2010

[Fr97] A. Frangioni
"Dual Ascent Methods
and Multicommodity Flow Problems" *Ph.D. Dissertation*
TD **5/97** (1997), Dip. di Informatica, Università di Pisa

[FrGa99] 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

[FrGe04] A. Frangioni, C. Gentile
"New
Preconditioners for KKT Systems of Network Flow Problems"
*SIAM Journal on Optimization* **14**(3), p. 894 - 913, 2004

[FrGe07a] A. Frangioni, C. Gentile
"Prim-based
Support-Graph Preconditioners for Min-Cost Flow Problems"
*Computational Optimization and Applications* **36**(2-3),
p. 271 - 287, 2007

[FrGe07b] A. Frangioni, C. Gentile
"Experiments
with Hybrid Interior Point/Combinatorial Approaches for Network Flow
Problems" *Optimization Methods and Software* **22**(4),
p. 573 - 585, 2007

[FGGP11] A. Frangioni, C. Gentile, E. Grande, A. Pacifici
"Projected
Perspective Reformulations With Applications in Design Problems"
*Operations Research* **59**(5), p. 1225 - 1232, 2011