Changes between Initial Version and Version 1 of MinCostFlowData

Timestamp:

10/25/13 16:23:25 (12 years ago)

Author:

Peter Kovacs

Comment:

First version

MinCostFlowData

@@ +1 @@
+= Benchmark data for the minimum-cost flow problem =
+
+This page provides a benchmark data suite for the minimum-cost network flow problem.
+
+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.
+
+
+== NETGEN instances ==
+These networks were generated with [ftp://dimacs.rutgers.edu/pub/netflow/generators/network/netgen/ NETGEN].
+
+'''Parameters:'''
+
+'''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:'''
+
+'''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:'''
+
+'''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:'''
+
+'''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/]