How to model $\max\limits_{x\in X} \min\limits_{y\in Y} \max\limits_{z\in Z} f(z)$ as single MILP

Question

I have the following optimization problem: \begin{align*} \max\limits_{x\in X} &\min\limits_{y\in Y} \max\limits_{z\in Z} & f(z) \\ &\text{such that} & (x, y, z)\in P \end{align*} where $X, Y, Z, P$ are polyhedrons, x must be integer, and $f$ is a linear function. Is there a way to model this as a linear program? In this question, there was a special case when the objective function was an integer variable. However, for my problem, I am having difficulty formulating it. The usual trick of formulating a simple bilevel maxmin/minmax problem doesn't work when I tried to do it twice in a row.

Answer 1

This is not a complete answer, but hopefully a direction to help formulating the MILP. Since $P,Y,Z$ are polyhedra, lets write it as $P = \lbrace{(x,y,z) | Ax+By+Cz \leq d \rbrace}$, let $f(z) = e^\top z$, $Y = \lbrace{y | Hy \leq m \rbrace}$ and $Z = \lbrace{z | Gz \leq k \rbrace}$. Let $Proj_{x}(P)$ denote the projection of $P$ onto $x$. You can rewrite your problem as: \begin{align*} \max\limits_{x\in X \cap Proj_{x}(P)} g(x) \end{align*} where \begin{align*} g(x) = &\min\limits_{y\in Y} \max\limits_{Gz \leq k} & e^{\top}z \\ &\text{such that} & Cz \leq d-Ax-By \end{align*} You can then apply duality to the inner maximization problem to obtain the following: \begin{align*} g(x) = &\min\limits_{y\in Y} \min\limits_{\lambda_1 \geq 0, \lambda_2 \geq 0} & \lambda_{1}^{\top} (d - Ax-By) + \lambda_{2}^{\top} k \\ &\text{such that} & C^{\top} \lambda_1 + G^{\top} \lambda_2 = e \end{align*} Since both are $min$ and $min$, we can collapse them both into a single minimization problem and represent it as: \begin{align*} g(x) = &\min\limits_{y, \lambda_1, \lambda_2} & \lambda_{1}^{\top} (d - Ax-By) + \lambda_{2}^{\top} k \\ &\text{such that} & C^{\top} \lambda_1 + G^{\top} \lambda_2 = e \\ && \lambda_1 \geq 0, \lambda_2 \geq 0\\ && Hy \leq m \end{align*} If the feasible region of the problem shown above is bounded, then $g(x)$ is convex in $x$. Computing $g(x)$ is computationally hard for arbitrary $B$ but can be posed as a MILP since it is equivalent to a bilinear function optimization. Maximizing $g(x)$ is equivalent to maximizing a concave function.