Return to Index
Operations Research Models and Methods
Computation Section

Jensen Solvers

LP/IP Solver

Enumeration Tree

Network Flow Programming Solver

Network Flow

Excel Page

Subunit Network Flow Programming Solver

A network flow solution algorithm is provided by the Network Solver add-in (net_solver.xla). The Excel Solver actually solves network problems by solving the underlying linear programming problem. Network algorithms are generally faster than linear programming algorithms for solving problems that can be modeled entirely as networks. This algorithm is used when the user chooses the Jensen Network Solver for either the Network or Transportation models of the Mathematical Programming add-in. The add-in must be installed prior to clicking on the Solve button for either case. The add-in works for linear problems that may or may not have integer variables.

There are no built-in limits for model size. Arrays are dimensioned automatically. For large problems, excessive memory requirements may cause the program to crash or computation time may be large.

The Jensen Network Solver add-in puts an item on the OR_MM menu: Network Solver. Choosing this item presents the dialog form shown below. The options on this dialog control the Jensen Network Solver. These options are particularly useful for the student interested in the procedures used in network optimization algorithms. The following describes the several categories of options appearing on this dialog.

Note that the Network Solver add-in only works for models constructed with the Math Programming add-in. A valid network model must be on the active worksheet when the Network Solver menu command is selected.

The solution parameters specified on this dialog are stored on the worksheet in column A starting at row 2.


Solution Display Options


These options print information on the problem worksheet or on a separate worksheet. The displays are useful for debugging algorithms, learning the principles of the algorithms and sensitivity analysis.

  • Show Dual Variables: Prints on the worksheet the node dual variables at optimality. Each node has a dual variable determined by the basis tree. The dual variables are shown to the right of the node external flow data.
  • Show Reduced Cost: Prints on the worksheet the arc reduced costs at optimality. Arcs are in three categories: basic arcs have a blue background color, nonbasic arcs with flow at the lower bound on a white background and arcs with upper bound flow with gray background. The reduced cost information is shown to the right of the arc data.
  • Show Basis: For a network flow problem, a basis is defined by a collection of arcs with one arc entering each node of the network. For a pure network problem the collection defines a tree. For the generalized problem it is a tree with one additional arc. When checked, the program displays the tree information to the right of the dual variables.
  • Simplex Iterations: This option creates a new worksheet with the suffix Details. Detailed information showing the iterations of the primal simplex are printed on this worksheet. The number field to the left on the dialog is the number of iterations to be displayed. Since some problems may require thousands of iterations, this number should be set to a reasonable value or the memory requirement for Excel will be excessive.
  • Enumeration Tree: This option displays on the Details worksheet information about the enumeration tree for integer problems. The number field to the left on the dialog is the number of branch and bound vertices to be displayed.

The figure below shows the worksheet for the Power example. The reduced costs are shown on the arc display in column M.


The dual variables basis tree information is shown on the node display.


The figure below shows the artificial arcs added prior to the beginning of the network simplex iterations. There is one artificial arc for each node. The computer adds three nodes to the original 6 nodes specified in the model. Node 7 is a super source node, node 8 is a super sink node, and node 9 is called the slack node. Four new arcs, 16-19, are added to connect the slack node to the super source and supper sink. The artificial arcs begin at arc 20.

The simplex iterations first drive out the artificial arcs from the basis during phase 1. The phase 2 iterations move toward the optimum basis obtained at iteration 14.

The enumeration tree is obtained for generalized problems (all gains not 1) when some arcs are required to have integer flows. The output is similar to that obtained with the Jensen LP/IP solver.


Algorithm Control Options

  • Initial Solution: Two different starting strategies are available. The first option starts with all arc flows equal to zero and an all artificial initial basis. The second strategy gathers the initial flows from the values shown on the worksheet. If a basis is displayed, the arcs listed are used as the initial basis. The algorithm starts with these values for the flows and the basis. The advanced start option will result in fewer iterations when only slight modifications are made to the network model.
  • MIP Tolerance: When solving all integer or mixed integer programming problems, vertices of the enumeration tree are fathomed when the relaxed solution objective is less than (for a maximization problem) than the incumbent solution. This tolerance makes the fathoming test a little easier by fathoming the vertex if its relaxed objective is within x% of the incumbent solution, where x is the number entered in this field. The solution may be found with fewer iterations and less time when this value is greater than 0. When the tolerance is other than 0, however, there is no guarantee that the optimum solution is obtained. It is a guaranteed that the solution is with x% of the optimum. The Excel Solver has a similar tolerance specified in the Options dialog of the Solver.
  • Time Limit: When solving all integer or mixed integer programming problems the process may take a long time. The program will stop when this time limit is reached. The user may give up at this point or continue the optimization. The Excel Solver has a similar time limit specified in the Options dialog of the Solver.
  • Update Incumbent on the Screen: When solving all integer or mixed integer programming problems, the algorithm may find feasible solutions during the enumeration process. The feasible solution with the best value is called the incumbent solution. Although intermediate steps are not displayed on the model worksheet while the process continues, when this checkbox is selected, the display will be changed whenever a new incumbent is discovered. For later versions of this add-in the incumbents are displayed automatically.


Return to Top

tree roots

Operations Research Models and Methods
by Paul A. Jensen
Copyright 2004 - All rights reserved