Based on this$^{[1]}$ question and this$^{[2]}$ post, I'm interested in rewriting piecewise linear constraints as equivalent sets of linear constraints in the context of an LP. In the following, let $x,y$ be scalar decision variables and let $c\in \mathbb{R}$.
Consider the piecewise linear constraint $$\max\{x,0\} \leq c \tag{1}$$ Can we rewrite (1) as the pair of constraints $$x \leq c,\quad 0 \leq c \tag{$1^*$}$$ I.e., are ($1$) and ($1^*$) equivalent?
Also, this reference [2] confused me. Here the author express $$\max\{x,0\} \geq c \tag{$2$}$$ as \begin{align} c \geq x + |x - y|, \quad c \geq y + |x - y| \end{align} (before breaking down the absolute values into penalized linear constraints). This led me to a few questions:
- can we reverse the inequality in ($2$) to get it in a form equivalent to ($1$) where the author's reformulation works?
- why does $|x-y|$ come in? the author's translation between $\min$ and $\max$ feels circular, so there must be something I'm missing...
- if ($1$) and ($1^*$) are not equivalent, is the reason due to no penalty (I'm assuming that the penalty should be added to the objective, kinda like an exact penalty method)
Thanks!
(1) and (1*) are equivalent.
In the second part you messed something up with the formulas. You can write (2) as
$$ \begin{array}{l} x=x^+-x^-\\ x^+,x^-\geq 0\\ c\leq x^+ \end{array} $$
as long as you ensure that at most one of $x^+,x^-$ is nonzero. That you can do with a binary variable. In general you cannot linearize it completely because $\max(x,0)$ is not concave.