Networks and the Network Simplex Algorithm

PROC NETFLOW’s network simplex algorithm solves pure network flow problems and network flow problems with linear side constraints. The procedure accepts the network specification in formats that are 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 specialized for network structures. 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.

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; therefore, any model-building techniques that apply to models for PROC LP also apply to network flow models having side constraints.

Problem data specified in the format used by the NETFLOW procedure can be readily reformatted for use with the newer OPTLP procedure. The MPSOUT= option in the NETFLOW procedure enables you to convert data in the format used by the NETFLOW procedure into an MPS-format SAS data set for use with the OPTLP procedure. For more information about the OPTLP procedure, see Chapter 17, The OPTLP Procedure. For more information about the MPS-format SAS data set, see Chapter 16, The MPS-Format SAS Data Set.

Linear and Network Programs Solved by the Interior Point Algorithm

The data required by PROC NETFLOW for a linear program resemble the data for nonarc variables and constraints for constrained network problems. They are similar to the data required by PROC LP.

The LP representation requires a data set that defines the variables in the LP using variable names, and gives objective function coefficients and upper and lower bounds. In addition, a constraint data set can be included that specifies any constraints.

When solving a constrained network problem, you can specify the INTPOINT option to indicate that the interior point algorithm is to be used. The input data are the same whether the simplex or interior point method is used. The interior point method is often faster when problems have many side constraints.

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; therefore, any model-building techniques that apply to models for PROC LP also apply to LP models solved by PROC NETFLOW.

Problem data specified in the format used by the NETFLOW procedure can be readily reformatted for use with the newer OPTLP procedure. The MPSOUT= option in the NETFLOW procedure enables you to convert data in the format used by the NETFLOW procedure into an MPS-format SAS data set for use with the OPTLP procedure. For more information about the OPTLP procedure, see Chapter 17, The OPTLP Procedure. For more information about the MPS-format SAS data set, see Chapter 16, The MPS-Format SAS Data Set.