The NETFLOW Procedure

Pricing Strategies

Subsections:

The pricing strategy is the part of the simplex iteration that selects the nonbasic arc, constraint slack, surplus, or nonarc variable that should have a flow or value change, and perhaps enter the basis so that the total cost incurred is improved.

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 strategies:

  • PRICETYPEx=NOQ

  • PRICETYPEx=BLAND

  • PRICETYPEx=Q

The pricing strategy that usually performs better than the others is PRICETYPEx=Q. For this reason, PRICETYPEx=Q is the default.

PRICETYPEx=NOQ

PRICETYPEx=NOQ is the least complex pricing strategy, but it is nevertheless quite efficient. In contrast to the specification of PRICETYPEx=Q, a candidate queue is not set up.

The PxSCAN= option controls the amount of additional candidate selection work done to find a better candidate after an eligible candidate has been found.

If PxSCAN=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 PxSCAN=BEST is specified, everything that is nonbasic is examined, and the best candidate of all is chosen.

If PxSCAN=PARTIAL is specified, once an eligible candidate is found, the scan continues for another PxNPARTIAL= 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 PxSCAN=FIRST or PxSCAN=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, the next iteration’s 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.

PRICETYPEx=Q

If PRICETYPEx=Q, a queue is set up. Candidates currently on the queue are tested at each iteration and either enter the basis or are removed from the queue. The size of the queue can be specified by using the QSIZEx= option. The default value for QSIZE1= is 

  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

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 PxSCAN=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 PxSCAN=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 PxSCAN=PARTIAL, PxNPARTIAL= can then be also specified. After an eligible candidate has been found, PxNPARTIAL= more queue members are examined and the best of the eligible candidates found is chosen.

When PxSCAN=FIRST or PxSCAN=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 QSIZEx= times REFRESHQx= iterations have been executed since the queue was last refreshed, new candidates are found and put onto the queue. Valid values for the REFRESHQx= options are greater than 0.0 and less than or equal to 1.0. The default for REFRESHQx is 0.75. If the scan cannot find enough candidates to fill the queue, the procedure reduces the value of QSIZEx=. If $\mi{qfound}$ is the number of candidates found, the new QSIZEx= value is $ \mi{qfound} + (( \mi{old\ QSIZEx} - \mi{qfound} ) \times \mi{REDUCEQSIZEx} )$. Valid values of the REDUCEQSIZEx= option are between 0.0 and 1.0, inclusive. The default for REDUCEQSIZEx= is 1.0.

The QxFILLSCAN= 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 QxFILLSCAN=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. QxFILLSCAN=FIRST is the default.

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

If QxFILLSCAN=PARTIAL is specified, after the queue is full, the scan continues for another QxFILLNPARTIAL= cycles in the hope that during the additional scan, better candidates are found to replace other candidates previously put onto the queue. QxFILLNPARTIAL=10 is the default. If QxFILLSCAN=FIRST or QxFILLSCAN=PARTIAL, the scan starts where the previous iteration ended; that is, it is wraparound.

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.

PRICETYPEx=BLAND

PRICETYPEx=BLAND is equivalent to specifying in the PROC NETFLOW or RESET statement all three options PRICETYPEx=NOQ, PxSCAN=FIRST, and LRATIOx, and the scans are not wraparound. Bland (1977) proved that this pivot rule prevents the simplex algorithm from cycling. However, because the pivots concentrate on the lower indexed arcs, constraint slack, surplus, and nonarc variables, optimization with PRICETYPEx=BLAND can make the optimization execute slowly.