DIMACS maximum flow problems
DIMACS (Center for Discrete Mathematics and Theoretical Computer Science (see http://dimacs.rutgers.edu/))
has formulated some 'challenges' for some specific problem instances (see http://dimacs.rutgers.edu/Challenges/).
One of these challenges is network flows and matching  the first DIMACS implementation challenge.
One of these network flows are maximum flow problems:
The maximum flow problem is structured on a network.
Here the arc capacities, or upper bounds, are the only relevant parameters.
The problem is to find the maximum flow possible from some given source node
to a given sink node. All arc costs are zero.
Since the goal of the optimization is to minimize cost, the maximum flow possible
is delivered to the sink node. Applications of this problem include finding the
maximum flow of orders through a job shop, the maximum flow of water through a
storm sewer system, and the maximum flow of product through a product distribution
system, among others.
Network Structure

A network is a directed graph with n nodes and m arcs.

Nodes are identified by integers 1...n.

Graphs do not have to be symmetric: if an arc (v,w) is in the graph,
the reverse arc (w,v) does not have to be in the graph.

Parallel arcs are not allowed.

Selfloops are not allowed.

Arc capacities are 32bit signed integers.

The source and the sink are distinct.

The sink may be unreachable from the source.
The following information makes up a DIMACS maximum flow input file:
 comment lines
 problem line
 node descriptors
 arc descriptors
As noted above, information is collected into lines, which begin with
onecharacter designators. We describe each type of information line in turn.
 Comment Lines: Comment lines give humanreadable information about the file and
are ignored by programs. Comment lines can appear anywhere in the file. Each comment line
begins with a lowercase 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 maximum flow network instances
the problem line has the following format:
p max NODES ARCS
The lowercase character p signifies that this is a problem line. The
threecharacter problem designator max identifies the file as containing
specification information for a maximum 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. Node descriptors are of the form:
n ID WHICH
where ID is the node id and WHICH is s for the source and
t for the sink.
Two node descriptors, one for the source
and one for the sink, must appear between the problem line and the arc
descriptor lines.
 Arc Descriptors: There is one arc descriptor line for each arc in the network.
For a maximum flow instance, arc descriptor lines are of the following form.
a SRC DST CAP
The lowercase 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 CAP
field gives the arc capacity.
Input File Example :
The example network pictured here is followed by a corresponding DIMACS
maximum flow input file.
c This is a simple example file to demonstrate the DIMACS
c input file format for maximum flow problems. The solution
c vector is [5,10,5,0,5,5,10,5] with cost at 15.
c Problem line (nodes, links)
p max 6 8
c source
n 1 s
c sink
n 6 t
c Arc descriptor lines (from, to, capacity)
a 1 2 5
a 1 3 15
a 2 4 5
a 2 5 5
a 3 4 5
a 3 5 5
a 4 6 15
a 5 6 5
c
c End of file
lp_solve can read/write and solve these models via the xli_DIMACS XLI driver (see External Language Interfaces).
It reads such a model in above format and solves it via linear programming.
The xli can also generate a DIMACS formatted file.
For example:
lp_solve rxli xli_DIMACS maxflow.net
This gives as result:
Value of objective function: 45
Actual values of the variables:
C1 5
C2 10
C3 5
C4 0
C5 5
C6 5
C7 10
C8 5
Also from within the IDE, this XLI can be used. However, some entries
must be added in LpSolveIDE.ini (in the folder where the IDE is installed).
In the [XLI] section the following must be added:
lib6=xli_DIMACS
And a new section for the DIMACS XLI must also be added:
[xli_DIMACS]
extension=.net
language=DIMACS
Then make sure that the xli_DIMACS.dll is available for the IDE.
This must be done by placing this dll in the IDE folder or in the
Windows system32 folder.
Solution :
The solution vector of above example is [5, 10, 5, 0, 5, 5, 10, 5]
This must be interpreted as follows:
There are as many variables as there are arc descriptor lines in the input file and
they appear in the same order. So:
C1 specifies how much flow there is for the first arc definition, in this case from A > B
C2 specifies how much flow there is for the second arc definition, in this case from A > C
...
This means there is a flow of 5 from node A to B, a flow of 10 from node A to C, ...
The value of the objective of lp_solve doesn't give you much information.
It is the sum of all variables used.
Output :
The solution of the model can also be written in a DIMACS format:
 comment lines
 solution lines
 flow assignments
For each network problem, the solution is an integervalued 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 onecharacter
designators. We describe each type of information line in turn.
 Comment Lines: Comment lines give humanreadable information about the file and
are ignored by programs. Comment lines can appear anywhere in the file. Each comment line
begins with a lowercase character c.
c This is an example of a comment line.

Solution line.
The solution line contains the flow value and has the following format:
s VALUE
The lowercase character s signifies that this is a solution line.
The VALUE field
contains the value of the objective.

Flow assignments.
There is one flow assignment line for each arc in the input network.
These lines have the following format:
f SRC DST FLOW
The lowercase 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).
lp_solve can generate a solution file via the xli_DIMACS XLI driver (see External Language Interfaces).
For example:
lp_solve rxli xli_DIMACS maxflow.net wxlisol xli_DIMACS maxflow.sol
This generates the following solution contents:
c maxflow.net
c
c Dimacsformat maximum flow result file
c generated by lp_solve
c
c Solution
s 15
c
c SRC DST FLOW
f 1 2 5
f 1 3 10
f 2 4 5
f 2 5 0
f 3 4 5
f 3 5 5
f 4 6 10
f 5 6 5
c
c End of file
lp_solve can also generate a solution file with only nonzero values.
For example:
lp_solve rxli xli_DIMACS maxflow.net wxlisol xli_DIMACS maxflow.sol wxlisolopt "nz"
This generates the following solution contents:
c maxflow.net
c
c Dimacsformat maximum flow result file
c generated by lp_solve
c
c Solution
s 15
c
c Only nonzero flows are written
c SRC DST FLOW
f 1 2 5
f 1 3 10
f 2 4 5
f 3 4 5
f 3 5 5
f 4 6 10
f 5 6 5
c
c End of file
A testset of models can be found at the dimacs ftp site: ftp://dimacs.rutgers.edu/pub/netflow
See Also DIMACS minimum cost flow problems,
DIMACS assignment problems
