Operations Research Models and Methods / Computation / Mathematical Programming

Network Solver

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.

 

Solution Display Options

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.

Algorithm Control Options

Initial Solution

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.

MIP Tolerance

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.

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.

 



Updated 1/16/01
Operations Research Models and Methods

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