Cubic term linearization

Hi,

If I have a cubic term as x.y.v, where x and y are binary variables and v is a continuous variable. Can I linearize it by introducing an auxillary variable w = y.v and then introduce another auxillary variable z = x.w where each auxillary variable can be linearized as a product of a binary and a continous variable? How can I ensure that the result is (optimum and not sub-optimum) because of the local minima corresponding to this cubic term. What recommended solver options to accelerate the reporting of the result, since I need to get the average of 100-1000 runs.

Any suggestions are appreciated.

Kind Regards,
Sarah

1 Like

Yes, you can linearize x * y * v in this way. Alternatively, you can introduce w = x * y and z = w * v, where x * y is just the product of two binary variables — but you would have to try both ways to see which works better for your application. Since you are solving an equivalent linear problem, any of the linear mixed-integer solvers will give you a global minimum.

If you are using a recent version of a linear mixed-integer solver for AMPL, you can also ask AMPL’s solver interface to linearize either of the following expressions:

x * y * v
(if x = y = 1 then v else 0)

(For CPLEX you should use the cplexmp version in the distribution.) Since you are concerned with speed of solution, you should test these against the linearizations that you do “by hand” since they may take advantage of features of your particular problem. In either case, you should take care in specifying the bounds on v, since tighter bounds often lead to better results.

You may also want to experiment with different solvers. Each solver has somewhat different options, so any advice on speeding execution through option settings will depend on the solver that is used.

2 Likes