A network solution algorithm is provided by this addin. 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
addin. The addin must be installed prior to clicking on the Solve button
for either case. The addin only works for linear problems, not for problems
with integer variables or nonlinear cost functions.
The Jensen Network Solver addin 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 quasitree. 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 noninfinite 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 nonoptimum 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 nonoptimum. Each node is allowed to keep one candidate
arc. If one or more arcs adjacent to a node is nonoptimum, 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.
