Single-commodity Min-Cost Flow Problems

Last update: 02/04/2012

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

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.



Linear Min-Cost Flow Problems

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





Single-commodity NonLinear Network Design problems

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



Bibliography

[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