The OPTLP Procedure

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

Figure 5: Minimum-Cost Network Flow Problem: Data

You can use the following SAS statements to create the input data table ex8:

data mylib.ex8;
   input _id_ field1 $8. field2 $13. @28 field3 $13. field4 @56 field5 $13. field6;
   datalines;
1  NAME    .               .                    .      .                   .
2  ROWS    .               .                    .      .                   .
3  N       obj             .                    .      .                   .
4  E       balance['1']    .                    .      .                   .
5  E       balance['2']    .                    .      .                   .
6  E       balance['3']    .                    .      .                   .
7  E       balance['4']    .                    .      .                   .
8  E       balance['5']    .                    .      .                   .
9  E       balance['6']    .                    .      .                   .
10 E       balance['7']    .                    .      .                   .
11 E       balance['8']    .                    .      .                   .
12 COLUMNS .               .                    .      .                   .
13 .       x['1','4']      obj                  2      balance['1']        1
14 .       x['1','4']      balance['4']        -1      .                   .
15 .       x['2','1']      obj                  1      balance['1']       -1
16 .       x['2','1']      balance['2']         1      .                   .
17 .       x['2','3']      balance['2']         1      balance['3']       -1
18 .       x['2','6']      obj                  6      balance['2']        1
19 .       x['2','6']      balance['6']        -1      .                   .
20 .       x['3','4']      obj                  1      balance['3']        1
21 .       x['3','4']      balance['4']        -1      .                   .
22 .       x['3','5']      obj                  4      balance['3']        1
23 .       x['3','5']      balance['5']        -1      .                   .
24 .       x['4','7']      obj                  5      balance['4']        1
25 .       x['4','7']      balance['7']        -1      .                   .
26 .       x['5','6']      obj                  2      balance['5']        1
27 .       x['5','6']      balance['6']        -1      .                   .
28 .       x['5','7']      obj                  7      balance['5']        1
29 .       x['5','7']      balance['7']        -1      .                   .
30 .       x['6','8']      obj                  8      balance['6']        1
31 .       x['6','8']      balance['8']        -1      .                   .
32 .       x['7','8']      obj                  9      balance['7']        1
33 .       x['7','8']      balance['8']        -1      .                   .
34 RHS     .               .                    .      .                   .
35 .       .RHS.           balance['1']        10      .                   .
36 .       .RHS.           balance['2']        20      .                   .
37 .       .RHS.           balance['4']        -5      .                   .
38 .       .RHS.           balance['7']       -15      .                   .
39 .       .RHS.           balance['8']       -10      .                   .
40 BOUNDS  .               .                    .      .                   .
41 UP      .BOUNDS.        x['1','4']          15      .                   .
42 UP      .BOUNDS.        x['2','1']          10      .                   .
43 UP      .BOUNDS.        x['2','3']          10      .                   .
44 UP      .BOUNDS.        x['2','6']          10      .                   .
45 UP      .BOUNDS.        x['3','4']           5      .                   .
46 UP      .BOUNDS.        x['3','5']          10      .                   .
47 UP      .BOUNDS.        x['4','7']          10      .                   .
48 UP      .BOUNDS.        x['5','6']          20      .                   .
49 UP      .BOUNDS.        x['5','7']          15      .                   .
50 UP      .BOUNDS.        x['6','8']          10      .                   .
51 UP      .BOUNDS.        x['7','8']          15      .                   .
52 ENDATA  .               .                    .      .                   .
;

You can use the following call to PROC OPTLP to find the minimum-cost flow:

proc optlp
  presolver  = none
  printlevel = 2
  logfreq    = 1
  data       = mylib.ex8
  primalout  = mylib.ex8out
  algorithm  = ns;
run;

The optimal solution is displayed in Output 5.8.1.

The optimal solution is represented graphically in Figure 6.

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

The iteration log is displayed in Output 5.8.2.