## Pricing

PROC LP performs multiple pricing
when determining which
variable will enter the basis at each pivot (Greenberg 1978).
This heuristic can shorten execution time in many problems.
The specifics of the multiple pricing algorithm depend on
the value of the PRICETYPE= option.
However, in general, when some form of multiple pricing
is used, during the first iteration PROC LP places
the PRICE= nonbasic columns yielding the
greatest marginal improvement to the objective function
in a candidate list.
This list identifies a subproblem of the original.
On subsequent iterations, only the reduced costs for the
nonbasic variables in the candidate list are calculated.
This accounts for the potential time savings.
When either the candidate list is empty or the subproblem is
optimal, a new candidate list
must be identified and the process repeats.
Because identification of the subproblem requires pricing the
complete problem, an iteration in which this occurs is called
a *major iteration*.
A *minor iteration*
is an iteration in which only the subproblem is to be priced.
The value of the PRICETYPE= option determines the
type of multiple pricing that is to be used.
The types of multiple pricing
include partial suboptimization (PRICETYPE=*PARTIAL*),
complete suboptimization (PRICETYPE=*COMPLETE*), and complete
suboptimization with dynamically varying the value of PRICE= option
(PRICETYPE=*DYNAMIC*).

When partial suboptimization is used, in each minor iteration the
nonbasic column in the subproblem yielding the greatest marginal
improvement to the objective is brought into the basis and removed from
the candidate list. The candidate list now has one less entry. At each
subsequent iteration, another column from the subproblem is brought into
the basis and removed from the candidate list. When there are either no
remaining candidates or the remaining candidates do not improve the
objective, the subproblem is abandoned and a major iteration is
performed. If the objective cannot be improved on a major iteration, the
current solution is optimal and PROC LP terminates.

Complete suboptimization is identical to partial suboptimization with
one exception. When a nonbasic column from the subproblem is brought
into the basis, it is replaced in the candidate list by the basic column
that is leaving the basis. As a result, the candidate list does not
diminish at each iteration.

When PRICETYPE=*DYNAMIC*, complete suboptimization is performed,
but the value of the PRICE= option changes so that the ratio of minor
to major iterations is within two units of the PRICE= option.

These heuristics can shorten execution time for
small values of the PRICE= option.
Care should be exercised in choosing a value from
the PRICE= option because too large a value
can use more time than if pricing were not used.

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