A network flow solution algorithm is provided by the Network Solver add-in. 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 many not have integer variables.
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.
These options print information on the problem worksheet, on a separate worksheet, or displayed through a message box. They 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 blue 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 quasi-tree. 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 right is the number of iterations shown. 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 branch and bound tree for integer problems. The number field to the right is the number of branch and bound nodes shown.
Two different starting strategies are available. The first option starts with all 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 is useful when only slight modifications are made to the network model.
When solving all integer or mixed integer programming problems nodes of the branch and bound 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 nodes is within x% of the encumbent 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, but 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.
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.