3
$\begingroup$

We have a decision variable $0<y<1$ and the following constraint $$z=\frac{y^2-y+1}{y(1-y)},\tag{1}$$ We also have another constraint $$y=f(x),\tag{2}$$ where $f(x)$ is a linear function of $x$.

In other words, our primary decision variable is $x$.

$y$ and $z$ are auxiliary decision variables.

We would like to linearize constraint (1) by replacing it with its piece-wise linear approximation.

How can we do that?

If we divide the interval $(0,1)$ into $n$ pieces of equal length (assuming we know what the "best" $n$ is) and denote each piece by $r_i, i=1,\ldots,n$, define a new decision variable $w_i=1$ if and only if $y$ is in the $i$th interval and $w_i=0$ otherwise, then can we linearize (1) as $$z=\sum_{i=1}^{n}\left(\frac{r_i^2-r_i+1}{r_i(1-r_i)}\right)w_i$$

Does this make sense? If so, since we are talking about an interval $r_i$, which point in that interval is going to be the value of $r_i$?

Do we need to add another constraint as $$\sum_{i=1}^{n}w_i=1,$$ so we guarantee that $y$ is in one of those intervals?

$\endgroup$

2 Answers 2

4
$\begingroup$

Adding the last constraint is required to guarantee that only one of the $r_i$ values is selected for $y$.

However, you need an additional constraint to make the relationship between $y$, its piecewise linearisation variables and the remaining of the problem constraints (especially $y=f(x)$), such as:

$$y = \sum_{i=1}^{n} r_i \times w_i$$

$\endgroup$
2
  • $\begingroup$ Thank you. I'm still confused about $r_i$. If we set it to be the $i$th piece, what would be its value? I think if $n\rightarrow \infty$ then there exist an $i$ where $r_i=y$ so it's not approximation but if $n$ is not sufficiently large, what is the value of $r_i$? It can by any value in the interval $[r_i,r_{i+1}]$ no? $\endgroup$
    – user9659
    Jan 22 at 17:03
  • $\begingroup$ You mean the value of $y$ as a function $r_i$ if $n$ is large enough or not. You may refer to @prubin's answer if you consider a linearization that implies $y \in [ r_i, r_{i+1} ]$. This means that any value in the interval $[ r_i, r_{i+1} ]$ is a solution to the problem. Another way of considering the linearization is to only consider one value for $y$. This means that if a $w_i=1$, then $y=r_i$. This is a stricter way of finding optimal values of $y$. $\endgroup$
    – Betty
    Jan 23 at 12:47
3
$\begingroup$

I assume that $y$ is constrained to the interval $[0,1]$. (You did not state this explicitly.) Let's assume that you have selected values $r_i$ such that $0=r_1 < r_2 < \dots < r_n = 1.$ If your solver supports SOS2 constraints, you can make $w_1, \dots, w_n$ nonnegative variables with the constraint $\sum_i w_i = 1$ and declare $\lbrace w_1,\dots,w_n\rbrace$ to be a type 2 special ordered set (meaning at most two of them can be nonzero, and those two must be consecutive). Then set $y=\sum_i r_i w_i.$ Your linearized formula for $z$ can be left as is, with the value of $z$ given $y$ being a weighted average of the $z$ values at the endpoints of the interval containing $y$.

How large to make $n$ is an empirical question. Larger $n$ means a better approximation but may increase solution time.

In choosing where to place the breakpoints $r_i$, you might want to refer to a plot of (1) as $y$ varies from 0 to 1. To get a better approximation of $z$, it usually helps to make the breakpoints denser in areas of steeper curvature and less dense where the graph is closer to being linear.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy