6

I'm trying to linearise these constraints, but I am not able to do correctly do it.

$$y_t = \max\{ y_{t-1} + a_t - z_t, 0 \} $$

My attempt was this:

\begin{align}y'_t &\geq a_t - z_t\\y'_t &\geq y^{'}_{t-1} + a_t - z_t \end{align}

Am I correct?

Additionally, I wanted to linearize this constraint: $$y_t = y_{t-1} + a_t - z_t + \min\{ y'_{t-1} + a_t - z_t,0 \}$$

This one I am clueless on. I will appreciate if anyone could please give any leads on this.

Kuifje
  • 13,324
  • 1
  • 23
  • 56

2 Answers2

5

If you are maximizing $y_t$ (or any increasing function of $y_t$) and using "standard" inequalities, you need something to preclude the solver from setting $y_t$ to $+\infty$. You can use the following constraints: \begin{align*} y_t &\le 0 +M(1-\delta) \tag{1}\\ y_t &\le y_{t-1}+a_t-z_t +M\delta \tag{2}\\ \delta &\in \{0,1\} \end{align*}

If $\delta =1$, constraint $(2)$ is inactive and $y_t$ will take value $0$, since you are maximizing $y_t$. If $\delta=0$, constraint $(1)$ is inactive and $y_t$ will take value $y_{t-1}+a_t-z_t$.

For your constraint, the same philosophy holds. You can replace $\min(u)$ by a variable $x$ and add the following constraints: \begin{align*} x &\le u \tag{3}\\ x &\le 0 \tag{4}\\ x &\ge u +M(1-\omega) \tag{5}\\ x &\ge 0 +M\omega \tag{6}\\ \omega &\in \{0,1\} \end{align*}

Kuifje
  • 13,324
  • 1
  • 23
  • 56
  • Would you know how to write this constraint in Pyomo, with $\delta$ ? –  Aug 04 '21 at 19:56
  • Additionally, how do I go about second part to my question, which is a linear combination, and I want to minimise. –  Aug 04 '21 at 19:57
  • now that I have updated the question, is it possible to help me with the second part too? –  Aug 05 '21 at 10:06
  • I don't fully understand the second part. What does it mean to "minimize a constraint" ? – Kuifje Aug 05 '21 at 10:34
  • If I have an equation such as $y = m + min(u)$, we want to linearise this equation, this is what I meant by minimise the constraint. Apologies for the lack of clarity. –  Aug 05 '21 at 10:52
  • you mean $\min(u,0)$ ? – Kuifje Aug 05 '21 at 11:03
  • yes this is what I mean –  Aug 05 '21 at 11:27
  • @Kuifje It might be clearer if you change $f(y_t)$ to $y_t$ at the start of your answer. Your current answer is correct if maximizing an increasing function $f()$ applied to $y_t$, but not if $f()$ is decreasing. – prubin Aug 06 '21 at 15:44
  • Yes indeed, thanks for pointing this out! – Kuifje Aug 06 '21 at 15:47
2

Without relying on whether the solver "prefers" larger or smaller values of $y_t$, you can introduce a binary variable $\delta$ and the following constraints:\begin{align*} y_{t} & \ge y_{t-1}+a_{t}-z_{t}\\ y_{t} & \ge0\\ y_{t} & \le y_{t-1}+a_{t}-z_{t}+M\delta\\ y_{t} & \le M(1-\delta). \end{align*} If $\delta=0$, this reduces to $y_t =y_{t-1} +a_t -z_t \ge 0$, while if $\delta=1$ it reduces to $y_t=0\ge y_{t-1} +a_t -z_t $.

For the second case, introduce a new variable $w_t$ to represent $\min\{ y'_{t-1} + a_t - z_t,0 \}$ and use the preceding with $y_t$ replaced by $w_t$ and with the four inequalities reversed.

prubin
  • 39,078
  • 3
  • 37
  • 104