Find min $ax+by+cz$ subject to $0 \le y \le 1, 0\le z \le 1$ and $\max(0,y+z-1) \le x \le \min(y,z)$ I am seeking an elegant way to solve the following problem.
Let $a,b,c$ be constant real numbers. Find min $ax+by+cz$ subject to $0 \le y \le 1, 0\le z \le 1$ and $\max(0,y+z-1) \le x \le \min(y,z)$. 
Thank you for any discussions.
 A: You can solve this using the simplex algorithm, if constants $a$ $b$ and $c$ are defined, but you need to linearize your problem first. Your problem is equivalent to
$$
\min\; ax+by+cz
$$
subject to
$$
 y \le 1\\
 z \le 1\\
x \le y\\
x \le z\\
y+z-1 \le x\\
x,y,z\ge 0
$$
A: I don't see a better way than a pretty large splitting of cases based on the sign of $a,b,c$
If $a,b,c$ are all positive, then te obvious solution is $x=y=z=0$.
If $a>0, b>0$ and $c<0$, then set $x=y=0$ and $z=1$ to get the minimum. Similarly if $a>0, b<0$ and $c>0$.

If $a>0$ and $b,c<0$, then you need to set $x$ to be as small as possible, and $y,z$ to be as large as possible, but the precise value depends on the exact values of $a,b,c$. Obviously, keeping $y,z$ the same and decreasing $x$ will decrease the end value. Also, if $y+z-1<0$, you can increase either $y$ or $z$ without touching $x$, and decrease the end value.
Therefore, so you can assume that $x=y+z-1\geq 0$, and you are basically looking for the minimum of $$a\cdot(y+z-1) + b\cdot y + c\cdot z$$ given $0\leq y,z\leq 1$  (since the demand $\max(0,y+z-1)\leq \min(y,z)$ holds automatically if $y+z\geq 1$).
You can rewrite that as finding the minimum of $a'y + b'z$ (plus a constant, but that's irrelevant) given $0\leq y,z\leq 1$, which again, you solve by looking at the signs of $a'$ and $b'$: if $a'>0$, set $y=1$, else set $y=0$. Same with $b'$ and $z$.

I don't really see how you can get out of this mess, other than a lot of case analysis...
