Piece-wise linear approximation of a constraint

Question

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?

Answer 1

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$$

Answer 2

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.