DIMACS MINIMUM-COST FLOW FILE FORMATS

(The information on this page is based on The First DIMACS International Algorithm Implementation Challenge: Problem Definitions and Specifications, available from the Center for Discrete Mathematics and Theoretical Computer Science.)

The DIMACS minimum-cost flow format requires that bounds on feasible arc flows be integer-valued (the LOW and CAP fields described below). All input and output files contain only ASCII characters with information collected on each line, as described below. A line is terminated with an end-of-line character. Fields in each line are separated by at least one blank space. Each line begins with a one-character designator to identify the line type.

Several problem instance generators for this format are available via anonymous ftp:

ftp://dimacs.rutgers.edu/pub/netflow/generators/network/

INPUT FILE FORMAT

The following information makes up a DIMACS minimum-cost flow input file:

comment lines
problem line
node descriptors
arc descriptors

As noted above, information is collected into lines, which begin with one-character designators. We describe each type of information line in turn.

Comment Lines: Comment lines give human-readable information about the file and are ignored by programs. Comment lines can appear anywhere in the file. Each comment line begins with a lower-case character c.
```
    c This is an example of a comment line.
```
Problem Line: There is one problem line per input file. The problem line must appear before any node or arc descriptor lines. For minimum-cost flow network instances the problem line has the following format:
```
    p min NODES ARCS
```
The lower-case character p signifies that this is a problem line. The three-character problem designator min identifies the file as containing specification information for a minimum-cost flow problem. The NODES field contains an integer value specifying n, the number of nodes in the network. The ARCS field contains an integer value specifying m, the number of arcs in the network.
Node Descriptors: All node descriptor lines must appear before all arc descriptor lines. For minimum-cost flow instances, the node descriptor lines describe supply and demand nodes, but not transshipment nodes. That is, only nodes with nonzero node supply values appear. There is one node descriptor line for each such node, with the following format.
```
    n ID FLOW
```
The lower-case character n signifies that this is a node descriptor line. The ID field gives a node identification number, an integer between 1 and n. The FLOW field gives the amount of supply at node ID.
Arc Descriptors: There is one arc descriptor line for each arc in the network. For a minimum-cost flow instance, arc descriptor lines are of the following form.
```
     a SRC DST LOW CAP COST
```
The lower-case character a signifies that this is an arc descriptor line. For a directed arc (v,w) the SRC field gives the identification number for the source vertex v, and the DST field gives the destination vertex w. Identification numbers are integers between 1 and n. The LOW field specifies the minimum abount of flow that can be sent along arc (v,w), and the CAP field gives the maximum amount of flow that can be sent along arc (v,w) in a feasible flow. The COST field contains the per-unit cost of flow sent along arc (v,w).

Input File Example :

The example network pictured here is followed by a corresponding DIMACS minimum-cost flow input file. Items listed in the lower-right of the graphic represent fields described above.

c
c        This is a simple example file to demonstrate the
c     DIMACS input file format for minimum-cost flow problems.
c 
c problem line :
p min 4 5
c
c node descriptor lines :
n 1 4
n 4 -4
c
c arc descriptor lines :
a 1 2 0 4 2
a 1 3 0 2 2
a 2 3 0 2 1
a 2 4 0 3 3
a 3 4 0 5 1

OUTPUT FILE FORMAT

The following information makes up a DIMACS output file:

comment lines
solution lines
flow assignments

For each network problem, the solution is an integer-valued flow assignment. The output file should list the solution and flow assignment for all arcs in the graph. As noted above, information is collected into lines, which begin with one-character designators. We describe each type of information line in turn.

Comment Lines: Comment lines are identical in form to those defined for input files. If there is no feasible solution then the algorithm may report this fact on a comment line (in such a case, neither solution lines nor flow lines will appear in the output).
Solution Lines: The solution line contains the solution value: that is, the cost of the minimum-cost feasible flow.
```
     s SOLUTION
```
The lower-case s signifies that this is a solution line. The SOLUTION field contains an integer corresponding to the solution value.
Flow Assignments: There is one flow assignment line for each arc in the network. Flow assignment lines have the following format.
```
     f SRC DST FLOW
```
The lower-case character f signifies that this is a flow assignment line. For arc (u,v), the SRC and DST fields give v and w, respectively. The FLOW field gives the amount of flow assigned to arc (u,v).

Output File Example :

The following DIMACS output file example corresponds to an optimal solution of the input example presented above.

c 
c This problem was processed by the Optimization Technology Center's
c NEOS Server for Linear Network Optimization (LNO).  
c 
c The problem was solved using RELAX-IV by Dimitri Bertsekas (MIT) and
c Paul Tseng (Univ. of Washington).  
c 
s     14.000000000000
f   1   2   2
f   1   3   2
f   2   3   2
f   2   4   0
f   3   4   4

[ OTC Home Page | NEOS Server | NEOS Guide ]