COIN-OR::LEMON - Graph Library

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:

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

GRIDGEN Instances

These networks were generated with GRIDGEN.

Parameters:

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

GOTO Instances

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

Parameters:

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

GRIDGRAPH Instances

These networks were generated with GRIDGRAPH.

Parameters:

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/

Last modified 3 years ago Last modified on 02/23/15 09:10:54

Attachments (13)

Download all attachments as: .zip