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

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)1, 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

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

• This can be reformulated as a geometric programming problem and solved exactly. See for instance docs.mosek.com/modeling-cookbook/… Dec 3, 2019 at 13:41

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.

• Thank you! Would you say there is any difference between the two formulations other than how the values of $x$ are discretized and selected? Dec 3, 2019 at 18:33
• Actually, if you choose to discretize let's say $x$ variable you should replace it with an equivalent discrete value, so you won't have $x$ in the objective function. Dec 3, 2019 at 19:05