PROC NETFLOW

Introduction to Optimization

PROC NETFLOW

Constrained network models describe a wide variety of real-world applications ranging from production, inventory, and distribution problems to financial applications. These problems can be solved with the NETFLOW procedure.

These models are conceptionally 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.

Certain algebraic features of networks are exploited by a specialized version of the Simplex method so that solution times are reduced. Another class of optimization algorithm, the Interior Point algorithm, has been implemented in PROC NETFLOW and can be used as an alternative to the Simplex algorithm to solve network problems.

Should NETFLOW detect there are no arcs and nodes in the model's data, (that is, there is no network component), it solves a linear programming (LP) problem. The Interior Point algorithm is automatically elected to perform the optimization. NETFLOW's ability to solve LP problems is an important ability new for the Version 7 release of the SAS System.

Networks and the Simplex Network Algorithm

PROC NETFLOW's network Simplex algorithm solves pure network flow problems and network flow problems with linear side constraints. The side constraints can have variables directly related to the network (called arc variables) as well as variables (called nonarc variables) that have nothing to do with the network. The procedure accepts the network specification in a format that is particularly suited to networks. Although network problems could be solved by PROC LP, the NETFLOW procedure generally solves network flow problems more efficiently than PROC LP.

Network flow problems, such as finding the minimum cost flow in a network, require model representation in a format that is simpler than PROC LP. The network is represented in two data sets: a node data set that names the nodes in the network and gives supply and demand information at them, and an arc data set that defines the arcs in the network using the node names and gives arc costs and capacities. In addition, a side-constraint data set is included that gives any side constraints that apply to the flow through the network. Examples of these are found later in this chapter.

$\begin{picture} (360,160) \thicklines \put(65,115){\makebox(0,0)[r]{Arc dat... ...(168,10){\makebox(0,0){\_ORNETFL}} \put(168,70){\vector(0,-1){50}}\end{picture}$

Figure 1.2: Input and Output Data Sets: PROC NETFLOW: Simplex Algorithm

The constraint data contains constraints that are not network flow conservation constraints. These can be specified in either the sparse or dense input formats. This is the same format that is used by PROC LP so that any of the model building techniques that apply to models for PROC LP also apply for network flow models having side constraints.

The NETFLOW procedure saves solutions in four data sets. Two of these store solutions for the pure network model, ignoring the restrictions imposed by the side constraints. The remaining two data sets contain the solutions to the network flow problem when the side contraints apply.

Network and Linear Programs solved by the Interior Point algorithm

The Simplex algorithm, developed shortly after World War II, was the main method used to solve Linear Programming problems. Over the last decade, 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 competivitely 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 solves Linear Programs, as well as network problems. When PROC NETFLOW detects that the problem has no network component, it automatically envokes the Interior Point aglorithm 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. It also is similar to the data required by PROC LP.

The LP is represented in one or two data sets: a data set that defines the variables in the LP using variable names and gives objective function coefficents and upper and lower bounds. In addition, a constraint data set can be includedthat gives any constraints.

$\begin{picture} (360,160) \thicklines \put(65,115){\makebox(0,0)[r]{Variabl... ...(168,10){\makebox(0,0){\_ORNETFL}} \put(168,70){\vector(0,-1){50}}\end{picture}$

Figure 1.3: Input and Output Data Sets: PROC NETFLOW: LP problems

When solving a constrained network problem, indicate that the Interior Point algorithm is to be used by specifying the INTPOINT option. The input data is the same whether the Simplex or Interior Point method is used. In other aspects of how PROC NETFLOW is used, there are only minor changes. The output, particularly the CONOUT data set where the solution is sent, is similar no matter which optimizer is used. The Interior Point method is often faster when problems have many side constraints.

$\begin{picture} (360,160) \thicklines \put(65,115){\makebox(0,0)[r]{Arc dat... ...(168,10){\makebox(0,0){\_ORNETFL}} \put(168,70){\vector(0,-1){50}}\end{picture}$

Figure 1.4: Input and Output Data Sets: PROC NETFLOW: Network problems: Intpoint algorithm

The constraint data can be specified in either the sparse or dense input format. This is the same format that is used by PROC LP so that any of the model building techniques that apply to models for PROC LP also apply for LP models solved by PROC NETFLOW.

Chapter Contents
Previous
Next
Top