Benchmark Data for the Minimum-Cost Flow Problem

This page provides benchmark input data for the minimum-cost network flow problem.

This test suite was used in the experiments of the paper:
Péter Kovács. ​Minimum-cost flow algorithms: an experimental evaluation. Optimization Methods and Software, 30:94-127, 2015. (A preliminary version can be accessed ​here.)

General Information

Most networks were generated with standard random generators: ​NETGEN, ​GRIDGEN, ​GOTO, and ​GRIDGRAPH, which are available at the ​FTP site of the ​1st DIMACS Implementation Challenge (1990-1991). Other instances were generated based on either real-life road networks or maximum flow problems arising in computer vision applications.

All instances are given in ​DIMACS format and contain only integer data.

Contact: Péter Kovács (kpeter [at] inf.elte.hu)

NOTE: download links are not guaranteed to be permanent. Please refer to this wiki page instead of the contained links:
http://lemon.cs.elte.hu/trac/lemon/wiki/MinCostFlowData

NETGEN Instances

These networks were generated with ​NETGEN.

Parameters:

• NETGEN-8 family: netgen_8.sh​
• NETGEN-SR family: netgen_sr.sh​
• NETGEN-LO-8 family: netgen_lo_8.sh​
• NETGEN-LO-SR family: netgen_lo_sr.sh​
• NETGEN-DEG family: netgen_deg.sh​

Download: ​http://lime.cs.elte.hu/~kpeter/data/mcf/netgen/

GRIDGEN Instances

These networks were generated with ​GRIDGEN.

Parameters:

• GRIDGEN-8 family: gridgen_8.sh​
• GRIDGEN-SR family: gridgen_sr.sh​
• GRIDGEN-DEG family: gridgen_deg.sh​

Download: ​http://lime.cs.elte.hu/~kpeter/data/mcf/gridgen/

GOTO Instances

These networks were generated with ​GOTO (Grid On Torus).

Parameters:

• GOTO-8 family: goto_8.sh​
• GOTO-SR family: goto_sr.sh​

Download: ​http://lime.cs.elte.hu/~kpeter/data/mcf/goto/

GRIDGRAPH Instances

These networks were generated with ​GRIDGRAPH.

Parameters:

• GRID-WIDE family: grid_wide.sh​
• GRID-LONG family: grid_long.sh​
• GRID-SQUARE family: grid_square.sh​

Download: ​http://lime.cs.elte.hu/~kpeter/data/mcf/gridgraph/

ROAD Instances

These instances were generated based on real-life road networks. We used the TIGER/Line data files of several states of the USA, which are available at the ​web site of the ​9th DIMACS Implementation Challenge (2005-2006): ​http://www.dis.uniroma1.it/challenge9/data/tiger/.

The cost of an arc is set to the travel time on the corresponding road section. The number of supply and demand nodes are both set to sqrt(n)/10 (where sqrt(n) denotes the square root of the number of nodes in the network). These nodes are selected randomly, and the supply-demand values are determined by a maximum flow computation.

• ROAD-PATHS family. The arc capacities are uniformly set to one.
• ROAD-FLOW family. The capacity of an arc is set 40, 60, 80, or 100 according to the road category.

Download: ​http://lime.cs.elte.hu/~kpeter/data/mcf/road/

VISION Instances

These instances were generated based on large-scale maximum flow problems arising in computer vision applications. The original maximum flow problem instances were made available by the ​Computer Vision Research Group at the ​University of Western Ontario. They can be accessed at ​http://vision.csd.uwo.ca/data/maxflow/.

We used some of the segmentation instances related to medical image analysis, which are defined on 3D grids (the bone_sub*_n6c100 files). These networks were converted to minimum-cost maximum flow problem instances applying different arc cost functions.

• VISION-RND family. The arc costs are selected uniformly at random.
• VISION-PROP family. The cost of an arc is approximately proportional to its capacity.
• VISION-INV family. The cost of an arc is approximately inversely proportional to its capacity.

Download: ​http://lime.cs.elte.hu/~kpeter/data/mcf/vision/