= 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. ''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/]