Introduction to Optimization


PROC NETFLOW

The NETFLOW procedure solves network flow problems with linear side constraints by using either a network simplex algorithm or an interior point algorithm.

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.

Network flow problems, such as finding the minimum cost flow in a network, benefit from 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 uses node names to define the arcs in the network 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 that have side constraints.

The Interior Point Algorithm

When you solve 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 network 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 network flow models that have side constraints. For more information about the NETFLOW procedure, see Chapter 5: The NETFLOW Procedure.