Linear program with $\max$ function in the objective that may lead to unboundedness

1.5k Views Asked by At

I am trying to solve the following linear program

$$\text{minimize} \quad \color{grey}{\text{(some cost function)}} - 24 \max(0,x-24)$$

I introduce a dummy variable $t$ such that $t \geq x-24$ and $t \geq 0$. I realized that if the variable $t$ is indeed greater than $0$, then it needs to be bounded above by some number, and the only appropriate number for my model has to be $x-24$ (due to the definition of $\max(0,x-24)$ being the excess quantity in my model). In other words, $t$ has to be exactly equal to $x-24$ if $x > 24$ or $0$.

I do not know how to work around this problem. Could anyone give some ideas? I hope I explain it well and any help would be appreciated!

1

There are 1 best solutions below

2
On BEST ANSWER

In general, you will need to introduce a binary variable. This requires have a valid lower bound $L$ and upper bound $U$ on the value of $x$. Given these bounds, introduce a binary variable $z\in\{0,1\}$. Then the constraints

$$ \left\{ \begin{array}{l} y\leqslant Uz\\ y\leqslant x-L(1-z)\\ y\geqslant0\\ y\geqslant x \end{array}\right. $$ will ensure that $y=\max\{0,x\}$. To see that this is true, consider two cases. If $z=0$, then $x\leqslant0$. The constraints become $$ \left\{ \begin{array}{l} y\leqslant 0\\ y\leqslant x-L\\ y\geqslant0\\ y\geqslant x \end{array}\right. \Longrightarrow \left\{ \begin{array}{l} y=0\\ x\geqslant{L}\ (\text{redundant})\\ x\leqslant0 \end{array}\right. $$ Otherwise, if $z=1$, then $x\geqslant0$, and the constraints become $$ \left\{ \begin{array}{l} y\leqslant U\\ y\leqslant x\\ y\geqslant0\\ y\geqslant x \end{array}\right. \Longrightarrow \left\{ \begin{array}{l} y=x\\ y=x\leqslant{U}\ (\text{redundant})\\ y=x\geqslant0 \end{array}\right. $$

See this helpful blog for a more general explanation.