How to linearize specific range constraints?

Question

I would like to know about the linearization of the $(If, Then)$ constraints as follows:

$$\begin{array}{l} \text { If: } \\ 15 \leqslant x \leqslant 25 \\ \text { then: } \quad y=\color{blue}{a} x+\color{green}{b} \\ \text { elself: } \\ 25 \leqslant x \leqslant 35 \\ \text { then: } \quad y=\color{blue}{a}^{\color{blue}{\prime}} x+\color{green}{b}^{\color{green}{\prime}} \\ \text { elself: } \\ 35 \leqslant x \leqslant 45 \\ \text { then: } \quad y=\color{blue}{a}^{\color{blue}{\prime \prime}} x+\color{green}{b}^{\color{green}{\prime \prime}} \\ \text { elself: } \\ 45 \leqslant x \leqslant 55 \\ \text { then: } \quad y=\color{blue}{a}^{\color{blue}{\prime \prime \prime}} x+\color{green}{b}^{\color{green}{\prime \prime \prime}} \\ \end{array}$$

Where $x$ and $y$ are continuous variables and $\color{blue}{a}$'s and $\color{green}{b}$'s are constant. We have tried to introduce the binary auxiliary variables for each set of constraints and finally linking these constraints with whose specific binary variable. This approach seems to work fine, but I am facing that we will have to use the product of the binary and continuous variables. I knew that we can use specific linearization to do this. I was wondering if, is there another way to formulate this problem efficiently?

Answer 1

Let $y_i$ be a binary variable that equals $1$ if and only if $x$ is in the interval $i \in \{[15,25],[25,35],[35,45],[45,55]\}$. You can express $x$ as a convex combination of the extreme points of these intervals by introducing variables $\lambda_0, \lambda_1,\lambda_2,\lambda_3, \lambda_4 \in \mathbb{R}^+$.

If $f$ denotes your piecewise linear function, the objective function is \begin{align*} &f(15)\lambda_0+f(25)\lambda_1+f(35)\lambda_2+f(45)\lambda_3 +f(55)\lambda_4 \\ =&(15a+b)\lambda_0+ (25a'+b')\lambda_1 +(35a''+b'')\lambda_2+ (45a'''+b''')\lambda_3 +(55a'''+b''')\lambda_4 \end{align*}

and the constraints are \begin{align*} 1 &= y_1+y_2+y_3+y_4 \tag{1}\\ x &= 15\lambda_0+25\lambda_1+35\lambda_2+45\lambda_3+55\lambda_4\tag{2}\\ 1 &=\lambda_0+\lambda_1+\lambda_2+\lambda_3 + \lambda_4\tag{3}\\ y_1&\le \lambda_0+\lambda_1\tag{4}\\ y_2&\le \lambda_1+\lambda_2\tag{5}\\ y_3&\le \lambda_2+\lambda_3\tag{6}\\ y_4&\le \lambda_3+\lambda_4\tag{7}\\ y&\in \{0,1\}\\ \lambda&\ge 0 \end{align*}

---

Another option, using the same binary variables $y_i$, is to rewrite $x$ in terms of $y_i$, and in terms of the ranges of each interval $x_i$: \begin{align*} x &= (15y_1+x_1)+(25y_2+x_2)+(35y_3+x_3)+(45y_4+x_4) \\ x_1 &\le 10 y_1 \\ x_2 &\le 10 y_2 \\ x_3 &\le 10 y_3 \\ x_4 &\le 10 y_4 \\ \end{align*} Make sure you are on exactly one interval: $$ y_1+y_2+y_3+y_4 = 1 $$ And rewrite your piecewise linear function as \begin{align*} f(x) &= \Big(a(x_1+15y_1) +by_1\Big) \\ &+\Big(a'(x_2+25y_2)+b'y_2\Big) \\ &+\Big(a''(x_3+35y_3)+b''y_3\Big) \\ &+\Big(a'''(x_4+45y_4)+b'''y_4\Big) \end{align*}

---

And last but not least, the usual (?) way with big Ms, maximize $z$ subject to:

\begin{align*} 1&=y_1+y_2+y_3+y_4 \\ x &\le 25y_1 + 35y_2 + 45y_3 +55 y_4 \\ x &\ge 15y_1 + 25y_2 + 35y_3 +45 y_4 \\ z &\le (ax+b) + M_1(1-y_1) \\ z &\le (a'x+b') + M_2(1-y_2) \\ z &\le (a''x+b'') +M_3(1-y_3) \\ z &\le (a'''x+b''') +M_4(1-y_4) \\ \end{align*}

Answer 2

If the $y$ function is continuous (meaning $a\cdot 25 + b = a^\prime \cdot 25 + b^\prime$ and similarly at other breakpoints), you can use an SOS2 constraint to model this. Let $p_0, \dots, p_n$ be the breakpoints ($n=4,\,p_0 = 15,\,p_4 =55$ in your example) and $\gamma_0 \dots, \gamma_n$ be the values of the $y$ function at $p_0, \dots, p_n$. Add continuous variables $w_0, \dots, w_n \in [0,1]$, along with the constraints \begin{align*} w_{0}+\dots+w_{n} & =1\\ p_{0}w_{0}+\dots+p_{n}w_{n} & =x\\ \gamma_{0}w_{0}+\dots+\gamma_{n}w_{n} & =y. \end{align*} Now add a constraint telling the solver that $w_0, \dots, w_n$ form a type 2 special ordered set (SOS2). That tells the solver that at most two of the $w_i$ can be nonzero, and those two must be consecutive. Combined with the first constraint, that means $x$ will be a convex combination of two consecutive breakpoints and $y$ will be the same convex combination of the function values at those two breakpoints.

This of course requires a solver that understands SOS2 constraints. Internally, the solver is likely to add a bunch of binary variables and basically do the linearization for you.