Network Flow Programming

To enter the model in the form of a network, select Network from the OR_MS menu. The Network Model Dialog allows the specification of a name, indication of maximization or minimization for the optimization, indication of whether the problem is linear or nonlinear, specification of the numbers of arcs and nodes and identification of integer flows on the arcs. Data is entered for the example problem.

The checkboxes near the middle of the dialog determines the set of parameters that will appear on the worksheet. We have unchecked the "Include Minimum" box because all the arcs have 0 arc lower bounds. When data for minimum flows are not shown, the assumption is that arc flows are nonnegative. With the "Include Maximums" box checked, a column will be included for the maximum values of flows. If it were not checked, the default is that arc flows are unbounded from above. With the "Include Gains" box checked a column will be included for arc gains. The default assumption is that arc gains are all 1. The "Sensitivity Analysis" box tells the selected solver to perform a sensitivity analysis on the optimum solution. The "Make Random Problem" box generates a random network. This is convenient for demonstrating the network modeling and solving options.

We see three solver options at the bottom of the dialog: Excel Solver, Jensen Network Solver and the Jensen LP Solver. Any one of these can solve the linear network flow problem with or without integer requirements. Only the Excel Solver can solve nonlinear problems. The Jensen Network Solver does not provide sensitivity analyses.

The worksheet showing the model for the Power problem is shown after data has been entered for the arc and node parameters and after the problem has been solved. Column D holds arc names. In this case we have chosen to name each arc by the node names at its ends. Columns F through J hold the arc parameters. Columns F and G contain the indices of the nodes that originate and terminate the arcs. Columns H through J hold the remaining parameters of the arcs. Lower bounds on arc flows are assummed to be zero since that column was not included in the display. The Upper column specifies the upper bound. The transmission arcs for this case have bounds of 10^10, the large upper bound not restricting the flow. The Cost column contains the unit cost of arc flow, and the Gain column holds the multipliers for arc flows. The variables for this problem are contained in the Flow column, column E. The flow in an arc is the flow leaving the origin node of the arc. The numbers shown in the illustration are the optimum values obtained by the Solver program. The column labeled Flow_O, column K, contains the flows entering the terminal nodes of the arcs. This is provided by an equation that multiplies the flow and the gain. The numbers in this column are used elsewhere on the worksheet and the formulas should not be changed.

Notice that arcs 13, 14 and 15 do not have origin nodes in the figure defining the problem. Rather, these arcs bring flow into the network at the nodes representing the power plant. This is shown in column F by specifying 0 as the origin node of these arcs. Similarly, an arc that starts at some network node and leaves the network is assigned 0 as the terminal node.

Information associated with the nodes is shown in the portion of the worksheet starting in column M. Node indices appear in column M, and names are provided by the user in column N. Fixed flows entering or leaving the node are in Column O. A positive number in this column is a flow that enters at the node, while a negative number is a flow that leaves. In the example, the negative numbers for nodes X, Y and Z are the power demands at the cities.

Column P of the node display, Balance, holds the equations that define conservation of flow for each node. Conservation of flow requires that total flow out of each node equal the total flow in. Formulas in these cells compute the net flow in or out of the cells. Feasible solutions require that the numbers in the Balance column all be zero. The solution shown here has very small values for the balance equations indicating that the solution is feasible within the numerical accuracy associated with the Solver program.

Updated 1/16/01

Operations Research Models and Methods

by Paul A. Jensen and Jon Bard, University of Texas, Copyright by the Authors