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 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.
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, 2000 nodes, and 3000 nodes. 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