Reformulation-linearization technique

From Glossary

Jump to: navigation, search

(RLT). The Reformulation-linearization-technique (rlt) is a general methodology for recasting difficult optimization problems into higher-dimensional spaces for the purpose of obtaining tight bounds. As suggested by the name, it consists of the two basic steps of reformulation and linearization. Given a mixed 0-1 linear program in LaTeX: n binary variables, the reformulation step creates additional redundant nonlinear constraints by multiplying the constraints by product factors of the binary variables LaTeX: x and their complements LaTeX: (1-x), and subsequently enforces the idempotent identity that LaTeX: x^2=x. The linearization step then substitutes a continuous variable for each distinct product of variables. A hierarchy of relaxations result, depending on the form of the product factors employed. An explicit algebraic characterization of the convex hull is available at the highest level, level-n. The method is also applicable to mixed 0-1 polynomial and to continuous, nonconvex programs. Furthermore, it can be applied to general discrete optimization problems by using product factors of Lagrange interpolating polynomials.

Personal tools