The NETFLOW Procedure

Introduction

The simplex algorithm, developed shortly after World War II, was the main method used to solve linear programming problems. Over the last fifteen years, the interior point algorithm has been developed to also solve linear programming problems. From the start it showed great theoretical promise, and considerable research in the area resulted in practical implementations that performed competitively with the simplex algorithm. More recently, interior point algorithms have evolved to become superior to the simplex algorithm, in general, especially when the problems are large.

The interior point algorithm has been implemented in PROC NETFLOW. This algorithm can be used to solve linear programs as well as network problems. When PROC NETFLOW detects that the problem has no network component, it automatically invokes the interior point algorithm to solve the problem. The data required by PROC NETFLOW for a linear program resembles the data for nonarc variables and constraints for constrained network problems.

If PROC NETFLOW does detect a network component to the problem (the problem has arcs), you must specify the option INTPOINT in the PROC NETFLOW statement if you want to use the interior point algorithm. PROC NETFLOW first converts the constrained network model into an equivalent linear programming formulation, solves that, then converts the LP back to the network model. These models remain conceptually easy since they are based on network diagrams that represent the problem pictorially. This procedure accepts the network specification in a format that is particularly suited to networks. This not only simplifies problem description but also aids in the interpretation of the solution. The conversions to and from the equivalent LP are done "behind the scenes."

There are many variations of interior point algorithms. PROC NETFLOW uses the Primal-Dual with Predictor-Corrector algorithm. This algorithm and related theory can be found in the texts by Roos, Terlaky, and Vial (1997), Wright (1996), and Ye (1996).

The remainder of this section is split into two parts. In the first part, how you use PROC NETFLOW's interior point algorithm to solve network problems is described. In the second part, using PROC NETFLOW to solve linear programming problems (its interior point algorithm must be used) is described. Both parts are organized similarly:

• The way data are supplied to PROC NETFLOW is outlined in a "Getting Started" subsection.
• An "Introductory Example" is solved to demonstrate how the data is set up, how PROC NETFLOW is used to compute the solution, and how the optimum is saved.
• More sophisticated ways to use PROC NETFLOW interactively are detailed in an "Interactivity" subsection.
• A "Functional Summary" lists the statements and options that can be used to control PROC NETFLOW. Of particular interest are the options used to control the optimizer, and the way the solution is saved into output data sets or is displayed.

The Linear Programs section has additional subsections:

• "Mathematical Description of LP"
• "Interior Point Algorithmic Details," a brief theory of the algorithm containing information about the options that can be specified to control the interior point algorithm.
• "Syntax" subsection, which is a subset of the syntax when the simplex algorithm is used. Gone are the statements and lists relevant only when the simplex algorithm is used.