5
$\begingroup$

Everyone knows how to model max-min or min-max problems. I have a problem with objective to maximize min-max. So it can be called as a max-min-max problem. Any ideas how to model it efficiently?

The objective function looks like: $$\max\quad\min_i\max_jx_{i,j}$$ where $x_{i, j}$ are integer variables.

$\endgroup$
1
  • 1
    $\begingroup$ Can you explicitly show us the objective? One possibility (perhaps not necessary?) is to formulate as a bilevel optimization problem having min-max as the inner problem, and max as the outer. $\endgroup$ Mar 28, 2022 at 17:55

1 Answer 1

6
$\begingroup$

Introduce binary variables $\lambda_{i,j}$ together with the constraints $$\sum_j \lambda_{i,j} = 1 \quad \forall i. \quad(1)$$ Next, add continuous variables $w_i$ defined by the constraints $$w_i =\sum_{j} \lambda_{i,j} x_{i,j}.\quad(2)$$If $x$ is a variable, there is a trick for linearizing the products $\lambda_{i,j} x_{i,j},$ documented in multiple answers on this site.

Finally, introduce a variable $z$ together with the constraints $$z\le w_i \quad \forall i \quad(3)$$and set the objective to maximize $z$. $z$ will be the minimum of the $w_i$, and for any $i$ where $z=w_i$ constraints (1) to (3) plus the goal of maximizing $z$ will ensure that $w_i$ is the largest of the $x_{i,j}.$

$\endgroup$
0

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.