5
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ Is $x$ bounded by $[15,55]$ or could it be outside of those four intervals? $\endgroup$
    – RobPratt
    Aug 3, 2021 at 12:57
  • $\begingroup$ @RobPratt, Thanks. It is bounded by $[15,55]$. $\endgroup$
    – A.Omidi
    Aug 3, 2021 at 12:58
  • $\begingroup$ Is the piecewise linear function convex and are you minimizing / is the piecewise linear function concave and are you maximizing ? Or neither ? $\endgroup$
    – Kuifje
    Aug 3, 2021 at 13:05
  • $\begingroup$ @Kuifje, the objective function is max. I am afraid, I do not understand what you mean by "Is the piecewise linear function ..."? $\endgroup$
    – A.Omidi
    Aug 3, 2021 at 13:13
  • $\begingroup$ Are the values of $a,a',...,b'''$ such that the union of $y=ax+b, ..., y=a'''x+b'''$ defines a concave function ? $\endgroup$
    – Kuifje
    Aug 3, 2021 at 13:14

2 Answers 2

7
$\begingroup$

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*}

$\endgroup$
4
  • $\begingroup$ Many thanks for your detailed explanation. Let's say, what we have tried to do is very close to your third formulation (as you mentioned the usual :)) But, for the last four constraints we define $[z1,z2,z3,z4]$ and trying to restrict the constraints by multiplying $y$'s variables directly to each constraint instead of using $big M$ and this is why we have faced non-linear term in the model. Finally, maximizing the objective function by summing them up. ($\sum_i z_i$). I tried your code and the results are the same. Thanks once again. $\endgroup$
    – A.Omidi
    Aug 3, 2021 at 20:04
  • $\begingroup$ I have another question. Would you say please, how we can express $x$ as a convex combination of the extreme points of these intervals? Your approach is very interesting in this specific problem. $\endgroup$
    – A.Omidi
    Aug 3, 2021 at 20:15
  • $\begingroup$ Equations $(1)-(3)$ are the convex combination part. I also like this method because it is very generic. But obviously it is not mine I read it somewhere a few years back ! $\endgroup$
    – Kuifje
    Aug 3, 2021 at 20:20
  • 1
    $\begingroup$ Note also that if the values of the constants $a,...,b'''$ are such that $f(x)$ is concave, there is a more efficient way. $\endgroup$
    – Kuifje
    Aug 3, 2021 at 20:21
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Many thanks for your suggestion. $\endgroup$
    – A.Omidi
    Aug 3, 2021 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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