# Presolve

### From Glossary

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 then simply fix 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 where B is a basis, and is a vector of costs associated with the basic variables. The vector is sometimes called a dual solution, though it is not feasible in the dual before termination. is also called a *simplex multiplier* or *pricing vector*. The price of the j-th variable is The first term is its *direct cost* 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 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 If then and 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 if and if Then, Thus, if activity must have a positive tableau value with respect to some basic variable whose level is zero, so the pivot would have to be degenerate.