1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.