Main Index Computation Index
Operations Research Models and Methods / Computation

Unit Network Flow Programming Solver


 

 

Return to Computation Menu

A network solution algorithm is provided by this 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 only works for linear problems, not for problems with integer variables or nonlinear cost functions.

The Jensen Network Solver add-in puts an item on the OR/MS 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, theory and application of 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.

  • 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. The Step is shown to the right of the tree arc range. It has relevance for the quadratic min cost flow problems. When using an advanced start for the algorithm, the procedure begins with the basis displayed on the worksheet, thus reducing computational effort. This option should be selected when the advanced start option is in effect.
  • Show 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.

Sequenced Solution Options

These options control the solution of a model with parallel arcs and sequence requirements.

  • Solve without Sequence: The Solver neglects the sequence information if this option is chosen. The optimum solution of the network model is obtained.
  • Solve with Sequence: The Solver uses a restricted basis entry simplex procedure to obtain a solution that satisfies the required sequence. The solution obtained will be a local optimum, but global optimality cannot be assured.
  • Show Gap: The Solver will first solve the problem without the enforcing the sequence and then solve the problem with the sequence required. The gap is difference between the two objective function values.

Nonlinear Solution Options

The Solver includes an algorithm to solve a model with separable quadratic arc costs. The method uses an implicit piecewise linearization of the cost functions. The user must select starting and ending step sizes for the linearization. The two values are entered into the indicated fields. The starting step size must be greater or equal to the ending step size. The starting size is adjusted to the next greater power of two, and the ending size is adjusted to the next smaller power of two. At the first iteration of the algorithm, the simplex procedure finds the optimum solution to with the starting step. The step size is cut in two, and the optimum is then found. The process continues until the minimum step size is reached.

The two values control the number of simplex iterations required. When solving the problem from a zero initial solution, the starting step size should be about half of the largest non-infinite upper bound and the ending step should be at the accuracy level desired for the final solution. The algorithm takes large steps at first and then smaller steps when approaching optimality. When solving from an advanced start after minor modifications of the model, the starting and ending step size can both be reasonably set to the desired accuracy level.

Algorithm Control Options

The algorithm can be controlled by the user through the method used to select a non-optimum arc to enter the basis and the initial solution.

Selecting the arc to enter the basis

There are three methods for selecting an arc to enter the basis. The primary methods are the candidate list and first select methods.

To create a candidate list, the entire list of arcs is inspected to see which are non-optimum. Each node is allowed to keep one candidate arc. If one or more arcs adjacent to a node is non-optimum, the one whose reduced cost most violates the optimality condition is listed for that node. Once the candidate list is constructed, the program picks arcs from that list to enter the basis. The list is sorted so that the arc that most violates optimality is chosen first. When all the arcs on the list have been used, a new list is generated.

The first select method goes through the list of arcs and evaluates the reduced cost of each. The first arc violating optimality conditions is selected to enter the basis.

The Candidate Control Field controls this aspect of the process. When set to 1, the candidate list procedure is used throughout the solution process. When set to 0 the first select method is used throughout the solution process. Say the field is set to 0.5. The candidate list method is used until fewer than half the nodes have candidates. Then the process switches to the first select method.

The Alternate select method is useful when the model includes parallel arcs or nonlinear arcs. For these models, certain arcs are more likely to violate optimality conditions than others. When the option is chosen, the algorithm quickly checks these arcs before the more complicated selection methods are used.

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.


Main Index Computation Index

Operations Research Models and Methods
by Paul A. Jensen and Jon Bard, University of Texas, Copyright by the Authors