2

An MINLP from a paper I am reading has the following expression in its constraints:

$$ p_{l,s}=z_lb_l\Delta\theta_{l,s}+b_l\lambda_{l,s}u_l\Delta\theta_{l,s} $$

Where from left to right:

$p_{l,s}$: continuous variable

$z_l$: binary variable

$b_l$: constant

$\Delta \theta_{l,s}$: continuous variable

$\lambda_l$: binary variable

$u_l$: binary variable

The authors of this paper replaces the second term with a continuous variable $\zeta$ as shown here:

$$ \xi_{l,s}:=b_lu_l\lambda_{l,s}\Delta\theta_{l,s} $$

The authors then mention:

By substituting this new variable for the third order polynomial, we are lifting the third order polynomial equation into a higher dimensional space and overcoming its nonlinearity.

What does that mean? what does overcoming the nonlinearity mean in this context?

RobPratt
  • 32,006
  • 1
  • 44
  • 84
Ahmed
  • 113
  • 4
  • 1
    For the general idea of lifting into a higher dimensional space, see https://or.stackexchange.com/questions/5906/how-to-implement-an-optimization-function-with-polynomial-in-gurobi-java/5908#5908 . As for the item in your question, presumably the authors mean that the model is linear in the new variable; although from your description, I'm not clear on the details of how they enforced that (presumably with some other constraint(s), perhaps aided by some of the variables being binary). Perhaps you can tell us what paper this is from, and provide a link? – Mark L. Stone Aug 11 '22 at 15:43

1 Answers1

2

Products of binary variables can be expressed as the logical and operation. The MILP formulation of that introduces a new binary variable. We overcome "non linearity" by having more dimensions and formulating a linear constraint in those higher dimension that when projected onto the original variables captures the non-linearity. Here is an example involving a product of {-1,0,1} originally we had 2 variables in {-1,0,1}. We introduced another variable so we had 3 variables in {-1,0,1}. Then we expressed those variables in {-1,0,1} as the difference of two booleans. So we went from the $\mathbb{Z}^2$ to the $\mathbb{Z}^6$ but got rid of all the non-linearity.

worldsmithhelper
  • 4,007
  • 6
  • 21