Reformulation Linearization Technique (RLT) cuts

Defines a Reformulation Linearization Technique (RLT) cut.

Reformulation Linearization Technique cuts, also known as RLT cuts, exploit a cutting plane technique to solve certain nonconvex continuous quadratic programs (QP) or mixed integer quadratic programs (MIQP) to global optimality.

Consider a conventional linearization of a possibly nonconvex QP:

x transpose time Q times x equals the pair Q, Y

where

As the first step in applying the reformulation linearization technique to this nonconvex model, multiply each valid constraint by a different variable. That is, consider a valid constraint, such as:

the sum of coefficient a sub j times variable x sub j less than or equal to b

Now consider another variable, such as:

the variable x sub i is greater than or equal to zero

Now consider their product. This step produces:

the sum of terms a sub j multiplied by x sub j multiplied by x sub i is less than or equal to b times x sub i

Next, use the relaxation variables

Y sub i and j equals x sub i times x sub j

to linearize that product:

the sum of terms a sub j multiplied by Y sub i and j is less than or equal to b times x sub i

The result is a cut. Moreover, this technique also works for equations with free variables.

For more detail about this subject, see the book A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems by Hanif D. Sherali and W. P. Adams, published in 1999 by Springer. For a discussion of mixed integer quadratic programs (MIQP) generally, see the article by Christian Bliek, Pierre Bonami, and Andrea Lodi, "Solving Mixed-Integer Quadratic Programming problems with IBM-CPLEX: a progress report" published in the Proceedings of the Twenty-Sixth RAMP Symposium of the Research Association of Mathematical Programming, held in Tokyo in 2014.