Is there a trick to linearise the product of two non-negative (decision) variables in linear optimisation?

Let $x_1$ and $x_2$ be these variables with $0 \leq x_1 \leq a$, $a \in \mathbb{R}_+$ and $b \leq x_2$, $b \in \mathbb{R}_+$.

I assume it is not possible because $x_2$ is not bounded above, but if I choose some large $M \in \mathbb{R}_+$ such that $b \leq x_2 \leq M$, then can the linearisation be done?

If not, what are good approximation techniques?

Thanks in advance!

  • $\begingroup$ Maybe you can take the logarithm of your variables since both your variables are positive. If $A$ is a subregion of $\mathbb{R}$. then $xy\in A \iff \log x + \log y \in \log A$. $\endgroup$
    – Marc
    Commented Jun 23, 2016 at 17:16
  • $\begingroup$ Thanks for your answer! However, I also have other linear (additivie) variables in the objective function (like $x_1 x_2 + a \cdot x_3 + b \cdot x_4$), so I don't think taking the logarithm would help. Are there other possibilities? $\endgroup$
    – anova
    Commented Jun 23, 2016 at 18:53
  • $\begingroup$ Edit: In the objective function also $x_1$ and $x_2$ are linearly present: i.e. $x_1 x_2 + a \cdot x_1 + b \cdot x_2 + c \cdot x_3$ $\endgroup$
    – anova
    Commented Jun 23, 2016 at 19:09
  • $\begingroup$ Quite a few solvers allow some forms of quadratic terms in the objective or the constraints (mostly convex only). Another possibility is a piecewise linear formulation (the easiest is to use a log transform y=log(x) so you don't have a 2d thing to linearize). $\endgroup$ Commented Jun 24, 2016 at 16:49


You must log in to answer this question.

Browse other questions tagged .