Minimize $\max (x_1, y_1, x_2, y_2) + \min (x_2, y_2) + z_1 + z_2$

Question

Minimize $\max (x_1, y_1, x_2, y_2) + \min (x_2, y_2) + z_1 + z_2$ where $x_1+x_2+y_1+y_2+z_1+z_2=1$ and $0 \leq x_1, x_2, y_1, y_2, z_1, z_2 \leq 1$

The only thing I can think to do is the standard multivariable calculus technique of looking for critical points and then optimizing over the boundary of this 5-dimensional domain. However, the problem "looks" so simple that I suspect there is an easier/more elegant way.

I've read about linear programming but only for linear objective functions, and this one is piecewise linear.

Answer 1

$$\begin{aligned} \min & \max (x_1, y_1, x_2, y_2) + \min (x_2, y_2) + z_1 + z_2 \\ & x_1+x_2+y_1+y_2+z_1+z_2=1 \\ & 0 \leq x_1, x_2, y_1, y_2, z_1, z_2 \leq 1\end{aligned}$$ is a bit complicated for an LP. The min max part is easy. The min min is non-convex and requires a binary variable:

$$\begin{aligned} \min\> & v_1 + v_2 + z_1 + z_2 \\ & v_1 \ge x_1 \\ & v_1 \ge y_1 \\ & v_1 \ge x_2 \\ & v_1 \ge y_2\\ & v_2 \le x_2 \\ & v_2 \le y_2 \\ & v_2 \ge x_2 - \delta \\ & v_2 \ge y_2 - (1-\delta) \\ & x_1+x_2+y_1+y_2+z_1+z_2=1 \\ & 0 \leq x_1, x_2, y_1, y_2, z_1, z_2 \leq 1 \\ & \delta \in \{0,1\} \\ & v_1,v_2 \ge 0 \end{aligned}$$

Here we have in the optimal solution: $v_1 = \max (x_1, y_1, x_2, y_2)$ and $v_2 = \min (x_2, y_2)$. With the presence of the binary variable $\delta$ we need a MIP solver (or solve two LPs, one with $\delta=0$ and one with $\delta=1$).