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

5
$\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$
    – Sigma
    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
4
$\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

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