I have two variables $x$ and $y$ which are bounded, $a<x<b$, $c<y<d$. I want to solve the following optimisation problem:
\begin{align} \text{max} |x-y| \\ \text{s.t. } a<x<b, \\ c < y <d . \end{align}
I want to relax this to a linear program but I'm not sure how to do this. I have seen a method of introducing an additional variable to solve the minimisation version of this problem (see Linear programming: minimizing absolute values and formulate in LP), however I was told this wouldn't work in the maximisation case.
Any suggestions or help would be appreciated.
This cannot be solved by a single LP, no matter what we try. There are two alternatives.
First, we could simply solve two LPs: one where we maximize $x-y$, and one where we maximize $y-x$. This is the most straightforward option.
Second, we could introduce a binary variable to help us select between the options, and use integer programming techniques. This could be done as follows: maximize $z$ subject to \begin{align} z &\le x-y + M\epsilon \\ z &\le y-x + M(1-\epsilon) \end{align} where $\epsilon \in \{0,1\}$ and $M$ is a very large number: large enough that when $\epsilon=1$, the first constraint doesn't restrict $z$, and when $\epsilon=0$, the second constraint doesn't restrict $z$. In this case, we have specific bounds on $x,y$ and so taking $M$ to be something like $2(b-a + d-c)$ could work.
The second option is less straightforward, but many LP solvers can also handle some binary variables thrown in, and it is often more efficient. If nothing else, it can save the common effort of finding an initial feasible solution for both linear programs.