Linearization of the product of two real valued variables - Binary expansion approach

Question

I want to minimize the following objective function:

\begin{align}\min &\quad x\cdot y\\\text{s.t.}&\quad2 \le x \le 5\\&\quad5 \le y \le 10.\end{align}

Since the objective function is a product of two real-valued variables, I am taking the following approach to linearize the problem using the binary expansion method. I pick the value of $x$ to discretize although either of the variables could be picked since the upper and lower bounds are known for both. So, I discretize the value of $x$ with a step value of $0.003$. Therefore, the sequence of $x$ values will look like this: $2, 2.003,2.006,\cdots,5$. Now, I implement the following optimization problem which is a mixed-integer linear program.

\begin{align}\min &\quad \sum_i x(i)\cdot p(i)\\\text{s.t.}&\quad\sum_i z(i) =1\\&\quad0 \le y-p(i) \le M\cdot(1-z(i))\\&\quad0 \le p(i) \le M\cdot z(i)\\&\quad5 \le y \le 10\end{align}

where, $M$ is the big-M value, $p(i)$ is an auxiliary real-valued variable and $z(i)$ is a binary variable. In Pereira et al. (2005)¹, however, they implement a different approach which is as follows when applied to my problem. First, they obtain discrete values of $x$ similar to my approach, where $x = \{x(i), i=0,1,\cdots,M\}$ and $M=2^K$ and $K$ is some non-negative integer. The optimization formulation is as follows:

\begin{align}\min&\quad x_{\rm LB}+\delta\cdot\sum_{i=0}^K 2^i\cdot p(i)\\\text{s.t.}&\quad0 \le y-p(i) \le M\cdot(1-z(i))\\&\quad0 \le p(i) \le M\cdot z(i)\\&\quad5 \le y \le 10\end{align}

where, $p(i) =y\cdot z(i)$, $\delta = (x_{\rm UB}-x_{\rm LB})/M$, $z(i)$ is a binary variable and $\rm LB$, $\rm UB$ refer to the lower and upper bound respectively. My question is while doing my linearization process, am I missing something in the first formulation compared to the second one? I appreciate your input on this.

---

_Reference

_{[1] Pereira, M. V., et al. (2005). Strategic Bidding Under Uncertainty: A Binary Expansion Approach. IEEE Transactions on Power Systems. 20(1):180-188.}

Answer 1

The notations that you used in the second formulation is confusing. I will reformulate your problem based on the approach that the authors explained on page 182 of the paper. In the following, I choose to discretize your continuous variable $x$. The binary expansion will be in the following form:

$$x=2+((5-2)/M_1) \sum_{i=0}^{K}2^i \cdot s_i$$ in which $M_1 = 2^{K}$ and $K$ is a nonnegative integer. Now by multiplying two sides of the above equation by $y$, you will be able to generate your objective function:

$$x \cdot y=2 \cdot y+((5-2)/M_1) \sum_{i=0}^{K}2^is_i \cdot y$$

Define the new variable $z_i =s_i \cdot y$:

$$x \cdot y=2 \cdot y+((5-2)/M_1) \sum_{i=0}^{K}2^i \cdot z_i$$ Now considering all of these changes, your model will be:

\begin{align} \min &\quad 2 \cdot y+((5-2)/M_1) \sum_{i=0}^{K}2^i \cdot z_i\\ \text{s.t.} &\quad 0 \le y-z_i \le G(1-s_i)\\ &\quad 0 \le z_i \le G \cdot s_i\\ &\quad 5 \le y \le 10 \end{align} where $G$ is a scalar value that is large enough for the first and second constraints to be relaxed when $s_i=0$ and $s_i=1$ respectively, based on the mentioned paper.