The Network Solver (Experimental)

Minimum-Cost Network Flow

Subsections:

Minimum Cost Network Flow for a Simple Directed Graph

The minimum-cost network flow problem (MCF) is a fundamental problem in network analysis that involves sending flow over a network at minimal cost. Let $G=(N,A)$ be a directed graph. For each link $(i,j) \in A$ , associate a cost per unit of flow, designated by $c_{ij}$ . The demand (or supply) at each node $i \in N$ is designated as $b_ i$ , where $b_ i \geq 0$ denotes a supply node and $b_ i < 0$ denotes a demand node. These values must be within $[b_ i^ l, b_ i^ u]$ . Define decision variables $x_{ij}$ that denote the amount of flow sent between node $i$ and node $j$ . The amount of flow that can be sent across each link is bounded to be within $[l_{ij}, u_{ij}]$ . The problem can be modeled as a linear programming problem as follows:

$\begin{alignat*}{3}& \text {minimize} & & \quad \sum _{(i,j) \in A} c_{ij} x_{ij} \\ & \text {subject to} & & \quad b_ i^ l \leq \sum _{(i,j) \in A} x_{ij} - \sum _{(j,i) \in A} x_{ji} \leq b^ u_ i & & \quad i \in N\\ & & & \quad l_{ij} \le x_{ij} \le u_{ij} & & \quad (i,j) \in A \end{alignat*}$

When $b_ i=b_ i^ l=b_ i^ u$ for all nodes $i \in N$ , the problem is called a pure network flow problem. For these problems, the sum of the supplies and demands must be equal to 0 to ensure that a feasible solution exists.

In the network solver, you can invoke the minimum-cost network flow solver by using the MINCOSTFLOW option.

The algorithm that the network solver uses for solving MCF is a variant of the primal network simplex algorithm (Ahuja, Magnanti, and Orlin 1993). Sometimes the directed graph $G$ is disconnected. In this case, the problem is first decomposed into its weakly connected components, and then each minimum-cost flow problem is solved separately.

The input for the network is the standard graph input, which is described in the section Input Data for the Network Solver. The MCF option uses the following suboptions of the LINKS= input option that specify link-indexed numeric arrays:

The WEIGHT= suboption defines the link cost $c_{ij}$ per unit of flow. (The default is 0, but if the WEIGHT= suboption is not specified, then the default is 1.)
The LOWER= suboption defines the link flow lower bound $l_{ij}$ . (The default is 0.)
The UPPER= suboption defines the link flow upper bound $u_{ij}$ . (The default is $\infty$ .)

The MCF option uses the WEIGHT= suboption of the NODES= option to specify supply. The parameter is a numeric array that is positive for supply nodes and negative for demand nodes.

The resulting optimal flow through the network is written to the link-indexed numeric array that is specified in the FLOW= suboption in the OUT= option in the SOLVE WITH NETWORK statement.

Minimum Cost Network Flow for a Simple Directed Graph

The following example demonstrates how to use the network simplex solver to find a minimum-cost flow in a directed graph. Consider the directed graph in Figure 8.38, which appears in Ahuja, Magnanti, and Orlin (1993).

Figure 8.38: Minimum-Cost Network Flow Problem: Data

The directed graph $G$ can be represented by the following links data set LinkSetIn and nodes data set NodeSetIn:

data LinkSetIn;
   input from to weight upper;
   datalines;
1 4 2 15
2 1 1 10
2 3 0 10
2 6 6 10
3 4 1  5
3 5 4 10
4 7 5 10
5 6 2 20
5 7 7 15
6 8 8 10
7 8 9 15
;

data NodeSetIn;
   input node weight;
   datalines;
1  10
2  20
4  -5
7 -15
8 -10
;

You can use the following call to the network solver to find a minimum-cost flow:

proc optmodel;
   set <num,num> LINKS;
   num cost{LINKS};
   num upper{LINKS};
   read data LinkSetIn into LINKS=[from to] cost=weight upper;
   set NODES = union {<i,j> in LINKS} {i,j};
   num supply{NODES} init 0;
   read data NodeSetIn into [node] supply=weight;
   num flow{LINKS};

   solve with network /
      loglevel        = moderate
      logfreq         = 1
      graph_direction = directed
      links           = (upper=upper weight=cost)
      nodes           = (weight=supply)
      mcf
      out             = (flow=flow)
   ;

   print flow;
   create data LinkSetOut from [from to] upper cost flow;
quit;

The progress of the procedure is shown in Figure 8.39.

Figure 8.39: Network Solver Log for Minimum-Cost Network Flow

NOTE: There were 11 observations read from the data set WORK.LINKSETIN.

NOTE: There were 5 observations read from the data set WORK.NODESETIN.

NOTE: The experimental Network solver is used.

NOTE: The number of nodes in the input graph is 8.

NOTE: The number of links in the input graph is 11.

NOTE: Processing the minimum cost network flow problem.

NOTE: The network has 1 connected component.

Primal Primal Dual

Iteration Objective Infeasibility Infeasibility Time

1 0.000000E+00 2.000000E+01 8.900000E+01 0.00

2 0.000000E+00 2.000000E+01 8.900000E+01 0.00

3 5.000000E+00 1.500000E+01 8.400000E+01 0.00

4 5.000000E+00 1.500000E+01 8.300000E+01 0.00

5 7.500000E+01 1.500000E+01 8.300000E+01 0.00

6 7.500000E+01 1.500000E+01 7.900000E+01 0.00

7 1.300000E+02 1.000000E+01 7.600000E+01 0.00

8 2.700000E+02 0.000000E+00 0.000000E+00 0.00

NOTE: The Network Simplex solve time is 0.00 seconds.

NOTE: The minimum cost network flow is 270.

NOTE: Processing the minimum cost network flow problem used 0.05 (cpu: 0.00)

seconds.

NOTE: The data set WORK.LINKSETOUT has 11 observations and 5 variables.

The optimal solution is displayed in Figure 8.40.

Figure 8.40: Minimum-Cost Network Flow Problem: Optimal Solution

Obs	from	to	upper	cost	flow
1	1	4	15	2	10
2	2	1	10	1	0
3	2	3	10	0	10
4	2	6	10	6	10
5	3	4	5	1	5
6	3	5	10	4	5
7	4	7	10	5	10
8	5	6	20	2	0
9	5	7	15	7	5
10	6	8	10	8	10
11	7	8	15	9	0

The optimal solution is represented graphically in Figure 8.41.

Figure 8.41: Minimum-Cost Network Flow Problem: Optimal Solution

Obs	from	to	upper	cost	flow
1	1	4	15	2	10
2	2	1	10	1	0
3	2	3	10	0	10
4	2	6	10	6	10
5	3	4	5	1	5
6	3	5	10	4	5
7	4	7	10	5	10
8	5	6	20	2	0
9	5	7	15	7	5
10	6	8	10	8	10
11	7	8	15	9	0

Obs	from	to	upper	cost	flow
1	1	4	15	2	10
2	2	1	10	1	0
3	2	3	10	0	10
4	2	6	10	6	10
5	3	4	5	1	5
6	3	5	10	4	5
7	4	7	10	5	10
8	5	6	20	2	0
9	5	7	15	7	5
10	6	8	10	8	10
11	7	8	15	9	0

Obs	from	to	upper	cost	flow
1	1	4	15	2	10
2	2	1	10	1	0
3	2	3	10	0	10
4	2	6	10	6	10
5	3	4	5	1	5
6	3	5	10	4	5
7	4	7	10	5	10
8	5	6	20	2	0
9	5	7	15	7	5
10	6	8	10	8	10
11	7	8	15	9	0