Minimisation problem obeying coupled inequalities

Question

I have a set of 4 two sided inequalities and 3 variables in the form

$ A[0] \le +Z + X \le B[0]$

$ A[1] \le +Z - X \le B[1]$

$ A[2] \le -Z + Y \le B[2]$

$ A[3] \le -Z - Y \le B[3]$

Where all A[j] < B[j], Ideally I would like to find a solution that satisfies these equations while minimising

$S = a |Z| + (1-a) (|X|+|Y|)$

with $0 \le a \le 1$, but I would settle for solutions with just a = 0 and a = 1. I'm not really sure where to start with this sort of problem, do I derive lots of sets of equations based on the signs elements in A and B?

Answer 1

You can solve this via linear programming by introducing additional variables $X'$, $Y'$, and $Z'$ and constraints: \begin{align} X' &\ge X \\ X' &\ge -X \\ Y' &\ge Y \\ Y' &\ge -Y \\ Z' &\ge Z \\ Z' &\ge -Z \\ \end{align} The new objective is to minimize $aZ'+(1-a)(X'+Y')$.