= 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:[[BR]]
''Péter Kovács. [http://www.tandfonline.com/doi/full/10.1080/10556788.2014.895828 Minimum-cost flow algorithms: an experimental evaluation]. Optimization Methods and Software, 30:94-127, 2015.''
(A preliminary version can be accessed [https://www.cs.elte.hu/egres/tr/egres-13-04.pdf here].)

== General Information ==

Most networks were generated with standard random generators:
[ftp://dimacs.rutgers.edu/pub/netflow/generators/network/netgen/ NETGEN],
[ftp://dimacs.rutgers.edu/pub/netflow/generators/network/gridgen/ GRIDGEN],
[ftp://dimacs.rutgers.edu/pub/netflow/generators/network/grid-on-torus/ GOTO], and
[ftp://dimacs.rutgers.edu/pub/netflow/generators/network/gridgraph/ GRIDGRAPH],
which are available at the [ftp://dimacs.rutgers.edu/pub/netflow/ FTP site]
of the [http://dimacs.rutgers.edu/Challenges/ 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 [http://lpsolve.sourceforge.net/5.5/DIMACS_mcf.htm 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:''[[BR]]
[http://lemon.cs.elte.hu/trac/lemon/wiki/MinCostFlowData]


== NETGEN Instances ==
These networks were generated with [ftp://dimacs.rutgers.edu/pub/netflow/generators/network/netgen/ NETGEN].

'''Parameters:'''
  * ''NETGEN-8 family'': [attachment:netgen_8.sh]
  * ''NETGEN-SR family'': [attachment:netgen_sr.sh]
  * ''NETGEN-LO-8 family'': [attachment:netgen_lo_8.sh]
  * ''NETGEN-LO-SR family'': [attachment:netgen_lo_sr.sh]
  * ''NETGEN-DEG family'': [attachment:netgen_deg.sh]

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


== GRIDGEN Instances ==
These networks were generated with [ftp://dimacs.rutgers.edu/pub/netflow/generators/network/gridgen/ GRIDGEN].

'''Parameters:'''
  * ''GRIDGEN-8 family'': [attachment:gridgen_8.sh]
  * ''GRIDGEN-SR family'': [attachment:gridgen_sr.sh]
  * ''GRIDGEN-DEG family'': [attachment:gridgen_deg.sh]

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


== GOTO Instances ==
These networks were generated with [ftp://dimacs.rutgers.edu/pub/netflow/generators/network/grid-on-torus/ GOTO] (Grid On Torus).

'''Parameters:'''
  * ''GOTO-8 family'': [attachment:goto_8.sh]
  * ''GOTO-SR family'': [attachment:goto_sr.sh]

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


== GRIDGRAPH Instances ==
These networks were generated with [ftp://dimacs.rutgers.edu/pub/netflow/generators/network/gridgraph/ GRIDGRAPH].

'''Parameters:'''
  * ''GRID-WIDE family'': [attachment:grid_wide.sh]
  * ''GRID-LONG family'': [attachment:grid_long.sh]
  * ''GRID-SQUARE family'': [attachment: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 [http://www.dis.uniroma1.it/~challenge9/ web site]
of the [http://dimacs.rutgers.edu/Challenges/ 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
[http://vision.csd.uwo.ca/ Computer Vision Research Group] at the
[http://www.csd.uwo.ca/ 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/]