In a linear program, I have a variable $y$ that must obey $y=\max(x-a,0)$ where $x$ is a linear combination of the other variables and $a$ is a constant. $x$ and $y$ and $a$ are always non-negative.
If the objective function decreases w.r.t. $y$, then adding the constraint $y\geq x-a$ makes it work.
Are there any way to add dummy varibles and contraints such that $y=\max(x-a,0)$ when the objective function increases w.r.t. $y$? I can't say $y\leq x-a$ because if $x-a<0$ it contradicts the non-negativity of $y$ whereby the solution might no longer be in the feasible region or the problem might even be infeasible.
Best Answer
Let $\bar{x} > a$ be a (small) constant upper bound on $x$. (If $\bar{x} \le a$, then $y=0$ always.) Introduce a binary variable $z$ and linear constraints \begin{align} y &\ge x - a \tag1 \\ y &\ge 0 \tag2 \\ y - x + a &\le a z \tag3 \\ y &\le (\bar{x}-a) (1-z) \tag4 \\ \end{align} Constraints $(1)$ and $(2)$ enforce $y \ge \max(x-a,0)$. Constraint $(3)$ enforces $z=0 \implies y \le x-a$. Constraint $(4)$ enforces $z=1 \implies y \le 0$.