Content deleted Content added
Line 23:
If the degree of ''f'' is greater than 2, one can always employ ''reductions'' to obtain an equivalent quadratic problem with additional variables.<ref name="ishikawa2011">Ishikawa, 2011</ref> One possible reduction is
:<math>\displaystyle -x_1x_2x_3=\min_{z\in\mathbf{B}}z(2-x_1-x_2-x_3)</math>
There are other possibilities, for example,
:<math> \displaystyle -x_1x_2x_3=\min_{z\in\mathbf{B}}z(-x_1+x_2+x_3)-x_1x_2-x_1x_3+x_1. </math>
Different reductions lead to different results. Take for example the following cubic polynomial:<ref name="kahlstrandmark">Kahl and Strandmark, 2011</ref>
:<math> \displaystyle f(\boldsymbol{x})=-2x_1+x_2-x_3+4x_1x_2+4x_1x_3-2x_2x_3-2x_1x_2x_3. </math>
Using the first reduction followed by roof duality, we obtain a lower bound of -3 and no indication on how to assign the three variables. Using the second reduction, we obtain the (tight) lower bound of -2 and the optimal assignment of every variable (which is <math> {(0,1,1)}</math>).
| |||