The OPTLP Procedure

The Network Simplex Algorithm

The network simplex algorithm in PROC OPTLP attempts to leverage the speed of the network simplex algorithm to more efficiently solve linear programs by using the following process:

  1. It heuristically extracts the largest possible network substructure from the original problem.

  2. It uses the network simplex algorithm to solve for an optimal solution to this substructure.

  3. It uses this solution to construct an advanced basis to warm-start either the primal or dual simplex algorithm on the original linear programming problem.

The network simplex algorithm is a specialized version of the simplex algorithm that uses spanning-tree bases to more efficiently solve linear programming problems that have a pure network form. Such LPs can be modeled using a formulation over a directed graph, as a minimum-cost flow problem. Let $G=(N,A)$ be a directed graph, where N denotes the nodes and A denotes the arcs of the graph. The decision variable $x_{ij}$ denotes the amount of flow sent from node i to node j. The cost per unit of flow on the arcs is designated by $c_{ij}$, and the amount of flow sent across each arc is bounded to be within $[l_{ij}, u_{ij}]$. The demand (or supply) at each node is designated as $b_ i$, where $b_ i > 0$ denotes a supply node and $b_ i < 0$ denotes a demand node. The corresponding linear programming problem is as follows:

\[ \begin{array}{rcccl} \mbox{min} & \sum _{(i,j) \in A} c_{ij} x_{ij} \\ \mbox{subject to} & \sum _{(i,j) \in A} x_{ij} - \sum _{(j,i) \in A} x_{ji} & = & b_ i & \forall i \in N \\ & x_{ij} & \le & u_{ij} & \forall (i,j) \in A \\ & x_{ij} & \ge & l_{ij} & \forall (i,j) \in A \end{array} \]

The network simplex algorithm used in PROC OPTLP is the primal network simplex algorithm. This algorithm finds the optimal primal feasible solution and a dual solution that satisfies complementary slackness. Sometimes the directed graph G is disconnected. In this case, the problem can be decomposed into its weakly connected components and each minimum-cost flow problem can be solved separately. After solving each component, the optimal basis for the network substructure is augmented with the non-network variables and constraints from the original problem. This advanced basis is then used as a starting point for the primal or dual simplex method. The solver automatically selects the algorithm to use after network simplex. However, you can override this selection with the ALGORITHM2= option.

The network simplex algorithm can be more efficient than the other algorithms on problems with a large network substructure. You can view the size of the network structure in the log.