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 12.5, which appears in Ahuja, Magnanti, and Orlin (1993).

Figure 12.5: Minimum-Cost Network Flow Problem: Data

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

data ex8;
   input field1 $8. field2 $13. @25 field3 $13. field4  @53 field5 $13. field6;
   datalines;
NAME    .               .                    .      .                   .
ROWS    .               .                    .      .                   .
N       obj             .                    .      .                   .
E       balance['1']    .                    .      .                   .
E       balance['2']    .                    .      .                   .
E       balance['3']    .                    .      .                   .
E       balance['4']    .                    .      .                   .
E       balance['5']    .                    .      .                   .
E       balance['6']    .                    .      .                   .
E       balance['7']    .                    .      .                   .
E       balance['8']    .                    .      .                   .
COLUMNS .               .                    .      .                   .
.       x['1','4']      obj                  2      balance['1']        1
.       x['1','4']      balance['4']        -1      .                   .
.       x['2','1']      obj                  1      balance['1']       -1
.       x['2','1']      balance['2']         1      .                   .
.       x['2','3']      balance['2']         1      balance['3']       -1
.       x['2','6']      obj                  6      balance['2']        1
.       x['2','6']      balance['6']        -1      .                   .
.       x['3','4']      obj                  1      balance['3']        1
.       x['3','4']      balance['4']        -1      .                   .
.       x['3','5']      obj                  4      balance['3']        1
.       x['3','5']      balance['5']        -1      .                   .
.       x['4','7']      obj                  5      balance['4']        1
.       x['4','7']      balance['7']        -1      .                   .
.       x['5','6']      obj                  2      balance['5']        1
.       x['5','6']      balance['6']        -1      .                   .
.       x['5','7']      obj                  7      balance['5']        1
.       x['5','7']      balance['7']        -1      .                   .
.       x['6','8']      obj                  8      balance['6']        1
.       x['6','8']      balance['8']        -1      .                   .
.       x['7','8']      obj                  9      balance['7']        1
.       x['7','8']      balance['8']        -1      .                   .
RHS     .               .                    .      .                   .
.       .RHS.           balance['1']        10      .                   .
.       .RHS.           balance['2']        20      .                   .
.       .RHS.           balance['4']        -5      .                   .
.       .RHS.           balance['7']       -15      .                   .
.       .RHS.           balance['8']       -10      .                   .
BOUNDS  .               .                    .      .                   .
UP      .BOUNDS.        x['1','4']          15      .                   .
UP      .BOUNDS.        x['2','1']          10      .                   .
UP      .BOUNDS.        x['2','3']          10      .                   .
UP      .BOUNDS.        x['2','6']          10      .                   .
UP      .BOUNDS.        x['3','4']           5      .                   .
UP      .BOUNDS.        x['3','5']          10      .                   .
UP      .BOUNDS.        x['4','7']          10      .                   .
UP      .BOUNDS.        x['5','6']          20      .                   .
UP      .BOUNDS.        x['5','7']          15      .                   .
UP      .BOUNDS.        x['6','8']          10      .                   .
UP      .BOUNDS.        x['7','8']          15      .                   .
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       = ex8
  primalout  = ex8out
  algorithm  = ns;
run;

The optimal solution is displayed in Output 12.8.1.

The optimal solution is represented graphically in Figure 12.6.

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

The iteration log is displayed in Output 12.8.2.