0

Problem Description:
I have a mixed integer linear optimization problem (MILP) with objective function $$\min_{x_{jt}} \sum_\omega \sum_j \sum_t y_{jt}(\omega)$$

I know $L_{jt}\le x_{jt}\le U_{jt}$ with $L_{jt}\ge 0$ and $L_{jt}\le U_{jt}$. We consider $b_{jt}(\omega)\ge 0$ known and provided as input data. We also know $x_{jt},y_{jt}\in \mathbb{R}^1$ and $0 \le y_{jt} \le y_{j,t-1} + b_{jt}$ for $t\ge 2$ with $0\le y_{j1} \le b_{j1}$ when $t=1$.

Question: Is it possible to use a MILP reformulation technique to address equality constraints of the following form? I would like to linearize these if possible. $$y_{jt}(\omega) = \max( b_{jt}(\omega)-x_{jt},0), \quad t=1,\forall j,\forall \omega$$ $$y_{jt}(\omega) = \max( b_{jt}(\omega)+y_{j,t-1}(\omega)-x_{jt},0), \quad t\ge2,\forall j,\forall \omega$$

SecretAgentMan
  • 109

1 Answers1

1

Since you already know that $y$ is nonnegative, you just need to add the constraint $$y_{j1}(\omega) \ge b_{j1}(\omega)-x_{j1}\, \forall j,\forall \omega.$$ Since the objective function minimizes the sum of the $y$ variables, you can be sure that $y_{j1}(\omega)$ will be no larger than it needs to be.

prubin
  • 4,923
  • Thank you @prubin for you advice. I will test this out.

    I apologize as I just realized my question wasn't complete so I've edited the question.

     – SecretAgentMan Jun 29 '18 at 14:15
  • 1
    There is one condition I forgot to mention. This only works if the other constraints do not "favor" a larger value of $y_{j1}(\omega)$. For instance, if you also add the constraints $y_{j1}(\omega) + y_{j2}(\omega)\ge K$, $y_{j1}(\omega) + y_{j3}(\omega) \ge K, \dots$, the solver might inflate the value of $y_{j1}(\omega)$ in order to reduce the value of other $y$ variables. So you need to look at the constraints as a whole before trusting this. The good news is you can try it, and you'll know if it works or not by checking equality of the max constraints. – prubin Jun 29 '18 at 14:40