From Glossary

Jump to: navigation, search

A heuristic applied to reduce the problem in some way before starting an algorithm. In linear programming, for example, one might scan for an equation of the form LaTeX: x=0, then simply fix LaTeX: x at zero, thus reducing the number of variables and constraints. Further details are in the supplement, simplex method, by which each variable is evaluated for its potential to improve the value of the objective function. Let LaTeX: p = c_B[B^{-1}], where B is a basis, and LaTeX: c_B is a vector of costs associated with the basic variables. The vector LaTeX: p is sometimes called a dual solution, though it is not feasible in the dual before termination. LaTeX: p is also called a simplex multiplier or pricing vector. The price of the j-th variable is LaTeX: c_j - pA_j. The first term is its direct cost LaTeX: (c_j) and the second term is an indirect cost, using the pricing vector to determine the cost of inputs and outputs in the activity's column LaTeX: (A_j). The net result is called the reduced cost, and its value determines whether this activity could improve the objective value.

Other pricing vectors are possible to obtain information about the activity's rates of substitution without actually computing LaTeX: \textstyle r = [B^{-1}]A_j. If LaTeX: \textstyle p = v[B^{-1}], then LaTeX: \textstyle pA_j = vr, and LaTeX: v = c_B is the special case to get the reduced cost. Another special case is to obtain information about whether the (nonbasic) activity would need to perform a degenerate pivot. For LP in standard from, let LaTeX: v_i=1 if LaTeX: x_i=0 and LaTeX: v_i=0 if LaTeX: \textstyle x_i > 0. Then, LaTeX: \textstyle vr = \sum_i \left \{r_i: x_i = 0\right\}. Thus, if LaTeX: pA_j > 0, activity LaTeX: j must have a positive tableau value with respect to some basic variable whose level is zero, so the pivot would have to be degenerate.

Personal tools