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.


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


1 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.

  • $\begingroup$ Thank you! Would you say there is any difference between the two formulations other than how the values of $x$ are discretized and selected? $\endgroup$
    – S_Scouse
    Dec 3, 2019 at 18:33
  • $\begingroup$ 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. $\endgroup$ Dec 3, 2019 at 19:05
  • $\begingroup$ I think $M_1 = 2^{K}$ is not correct, as it does not cancel itself out with $\sum_{i=0}^{K}2^i \cdot z_i$ for the case of all bits being set. Instead, it should be $M_1 = 2^{K+1} -1$. Is that possible? $\endgroup$ Apr 3 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.