Chapter Contents |
Previous |
Next |

The NETFLOW Procedure |

The pricing mechanism takes a large amount of computational effort, so it is important to use the appropriate pricing strategy for the problem under study. As in other large scale mathematical programming software, network codes can spend more than half of their execution time performing Simplex iterations in the pricing step. Some compromise must be made between using a fast strategy and improving the quality of the flow or value change candidate selection, although more Simplex iterations may need to be executed.

The configuration of the problem to be optimized has a great effect on the choice of strategy. If a problem is to be run repeatedly, experimentation on that problem to determine which scheme is best may prove worthwhile. The best pricing strategy to use when there is a large amount of work to do (for example, when a cold start is used) may not be appropriate when there is little work required to reach the optimum (such as when a warm start is used). If paging is necessary, then a pricing strategy that reduces the number of Simplex iterations performed might have the advantage. The proportion of time spent doing the pricing step during stage 1 optimization is usually less than the same proportion when doing stage 2 optimization. Therefore, it is more important to choose a stage 2 pricing strategy that causes fewer, but not necessarily the fewest, iterations to be executed.

There are many similarities between
the pricing strategies for optimizing
an unconstrained problem (or when constraints are temporarily
ignored) and the pricing mechanisms for optimizing considering
constraints.
To prevent repetition, options have a suffix or
embedded *x* .
Replace *x* with 1 for optimization without
constraint consideration and 2 for optimization with constraint
consideration.

There are three main types of pricing strategy:

- PRICETYPE
*x*=NOQ - PRICETYPE
*x*=BLAND - PRICETYPE
*x*=Q

The P*x*SCAN= option controls the amount of additional
candidate selection work
done to find a better
candidate after an eligible candidate has been found .
If P*x*SCAN=FIRST is specified,
the search for candidates finishes when the
first eligible candidate is found, with this exception:
if a node has more than one
eligible arc directed toward it, the best such arc is chosen.

If P*x*SCAN=BEST is specified, everything that is nonbasic is
examined, and the best candidate of all is chosen.

If P*x*SCAN=PARTIAL is specified,
once an eligible candidate is found, the scan continues
for another P*x*NPARTIAL=
cycles in the hope that during the additional scan, a better candidate
is found.
Examining all nonbasic arcs directed toward a single
node is counted as only one cycle.

If P*x*SCAN=FIRST or P*x*SCAN=PARTIAL is specified,
the scan for entering candidates starts where the last iteration's
search left off. For example, if the last
iteration's scan terminated after examining arcs that are directed toward
the node with internal number *i*, next iterations scan starts by
examining arcs directed toward the node with internal
number *i* + 1.
If *i* is the largest node number, next iterations scan begins by scanning arcs
directed toward node 1 (during stage 1) or scanning constraint slack or surplus
variables, if any, or nonarc variables, if any, (during stage 2).
During stage 2, if the scan terminated after examining the
slack or surplus of constraint *i*, next iterations scan starts by examining the
slack or surplus of the
constraint with the internal number greater than *i* that has such
a logical variable.
If the scan terminated after examining the
nonarc variable *i*, the next iterations scan starts by examining the
nonarc variable with internal number *i*+1, (or arcs directed to the node
with the smallest internal number if the nonarc variable with the
greatest number has been examined).
This is termed a *wraparound search* .

QSIZE1=number of arcs/200 if (QSIZE1<24) QSIZE1=24 else if (QSIZE1>100) QSIZE1=100

The default value for QSIZE2= is

QSIZE2=(number of arcs+number of nonarc variables)/200 if (QSIZE2<24) QSIZE2=24 else if (QSIZE2>100) QSIZE2=100

The P*x*SCAN= option controls the amount of additional
candidate selection work
done to find a better
candidate after an eligible candidate has been found *in the queue*.
If you specify P*x*SCAN=BEST,
the best eligible candidate found is removed from the queue.
It can sustain a flow or value change and possibly enter the basis.

If you specify P*x*SCAN=FIRST,
the first eligible candidate found is removed from the queue,
and possibly sustains a flow or value change and enters the basis.

If you specify P*x*SCAN=PARTIAL,
P*x*NPARTIAL= can then be specified as well.
After an eligible candidate has been found in the
P*x*NPARTIAL= more queue members are examined and the best of the eligible candidates
found is chosen.
When P*x*SCAN=FIRST or P*x*SCAN=PARTIAL,
the scan of the queue is wraparound.
When the member last added to the queue has been examined,
the scan continues from the member that was first added to the queue.

When the queue is empty,
or after QSIZE*x*= times REFRESHQ*x*= iterations have been
executed since the queue was last refreshed, new candidates are
found and put onto the queue.
Valid values for the REFRESHQ*x*= options are greater than 0.0
and less than or equal to 1.0.
The default for REFRESHQ*x* is 0.75.
If the scan cannot find enough candidates to fill the queue, the
procedure
reduces the value of QSIZE*x*=.
If *qfound* is the number of candidates found,
the new QSIZE*x*= value is
*qfound* + (( *old QSIZEx*= - *qfound* ) * *REDUCEQSIZEx*= ).
Valid values of the REDUCEQSIZE*x*= option are between 0.0 and 1.0, inclusive.
The default for REDUCEQSIZE*x*= is 1.0.

The Q*x*FILLSCAN= option controls the amount of additional
candidate selection work performed to
find better candidates to put into the queue after the queue has been
filled.
If you specify Q*x*FILLSCAN=FIRST, the nonbasic arcs, and during stage 2
optimization, nonbasic constraint
slack and surplus variables, and nonbasic nonarc variables are scanned;
the scan stops when the queue is filled.
If a node has more than one
eligible arc directed toward it, the best such arc is put onto the queue.
Q*x*FILLSCAN=FIRST is the default.

If Q*x*FILLSCAN=BEST is specified, everything that is nonbasic is scanned
and the best eligible candidates are used to fill the queue.

If Q*x*FILLSCAN=PARTIAL is specified,
after the queue is fill, the scan continues
for another Q*x*FILLNPARTIAL=
cycles in the hope that during the additional scan, better candidates
are found to replace other candidates previously put onto the queue.
Q*x*FILLNPARTIAL=10 is the default.
If Q*x*FILLSCAN=FIRST or Q*x*FILLSCAN=PARTIAL ,
the scan starts where the previous iteration ended; that is,
it is wrap-around.

In the following section, dual variables and reduced costs are explained.
These help PROC NETFLOW determine whether an arc, constraint slack, surplus,
or nonarc variable should have a flow or value change.
P2SCAN=ANY and the DUALFREQ= option can be specified to control stage 2 pricing,
and how often dual variables and reduced costs are calculated.
What usually happens when PRICETYPE2=Q is specified is
that before the first iteration,
the queue is filled
with nonbasic variables that are eligible to enter the basis.
At the start of each iteration, a candidate on the queue is examined
and its reduced cost is calculated to ensure that it is still
eligible to enter the basis.
If it is ineligible to enter the basis, it is removed from the queue
and another candidate on the queue is examined, until
a candidate on the queue is found that can enter the basis.
When this happens, a *minor* iteration occurs.
If there are no candidates left on the queue, or several iterations
have been performed since the queue was refreshed,
new nonbasic variables that are eligible to enter the basis are
found and are placed on the queue.
When this occurs, the iteration is termed a *major* iteration.
Dual variables are calculated or maintained every iteration.

During most optimizations, if a variable
is put onto the queue during a major iteration, it usually remains
eligible to enter the basis in later minor iterations.
Specifying P2SCAN=ANY indicates that PROC NETFLOW should choose
*any* candidate on the queue and use that as the entering variable.
Reduced costs are not calculated. It is simply hoped that
the chosen candidate is eligible.
Sometimes, a candidate on the queue is chosen that has become
ineligible and the optimization takes "a step backward"
rather than "a step forward" toward the optimum.
However, the disadvantages of incurring an occasional step backwards
and the possible danger of never converging to the optimum,
are offset by not having to calculate reduced costs and, more
importantly, not having to maintain dual variable values.
The calculation of dual variables is one of two large linear equation
systems that must be solved each iteration in the Simplex
iteration.

If P2SCAN=ANY is specified, dual variables are calculated after DUALFREQ= iterations have been performed since they were last calculated. These are used to calculate the reduced costs of all the candidates currently on the queue. Any candidate found to be ineligible to enter the basis is removed from the queue. DUALFREQ=4 is the default.

Once again, the practice of not maintaining correct dual variable values is dangerous because backward steps are allowed, so the optimization is not guaranteed to converge to the optimum. However, if PROC NETFLOW does not run forever, it can find the optimum much more quickly than when the P2SCAN= option is not ANY. Before concluding that any solution is optimal, PROC NETFLOW calculates true dual variable values and reduced costs and uses these to verify that the optimum is really at hand.

Whether P2SCAN=ANY is specified or not, dual variables are always calculated at the start of major iterations.

Chapter Contents |
Previous |
Next |
Top |

Copyright © 1999 by SAS Institute Inc., Cary, NC, USA. All rights reserved.