# Piece-wise linear approximation of a constraint

We have a decision variable $$0 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?

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

• 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?
– user9659
Commented Jan 22, 2022 at 17:03
• 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$. Commented Jan 23, 2022 at 12:47

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.