4
$\begingroup$

How to solve the following minimax problem quickly? The variables are all continuous.

$$\max_{x_{1}, x_{4}, x_{5}} \min_{x_2,x_3} \vec{c}^{\intercal} \vec{x}$$

subject to the following constraints: $$A\vec{x} \ge \vec{b}$$ $$\vec{x} \ge 0$$

where

$$A = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ -1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & -1 & -1 & 0 & 0 \\ 0 & -1 & 0 & 0.4 & 0 \\ 0 & 0 & -1 & 0 & 0.4 \\ 1 & 0 & 0 & -1 & -1 \\ 0 & -0.6 & 0 & 1 & 0 \\ 0 & 0 & -0.6 & 0 & 1 \end{bmatrix}$$

$$\vec{b}^{\intercal} = \begin{bmatrix} 1 & -1 & 2 & -2 & 1 & 1 & -1 & 0.6 & 0.6 \end{bmatrix}$$

$$\vec{c}^{\intercal} = \begin{bmatrix} 1 & -0.6 & -0.6 & 0 & 0 \end{bmatrix}$$

I tried to split the variables into two groups $x_1, x_4, x_5$ and $x_2, x_3$. And replace the inner minimization by its dual, which is a maximization. But that makes the objective function quadratic instead of linear:

$$ \max_{x_1, x_4, x_5} \left( \max_{x_2, x_3} \vec{b}^{\intercal} \vec{y} - \vec{x}^{\intercal}A_{1,4,5}^{\intercal} \vec{y} \right)$$ where $A_{1,4,5}$ is same as $A$ except columns 2 and 3 are all zeros.

$\endgroup$
5
  • $\begingroup$ Are you sure the problem is stated correctly? This is maximin instead of minimax. Also, the first two constraints imply that $x_1=1$, so you can eliminate that variable. $\endgroup$
    – RobPratt
    Aug 21, 2021 at 20:18
  • $\begingroup$ Yes. $x_1 = 1$, $x_2 + x_3 = 2$ Exchanging the order of max and min should be fine in this case because it is a zero-sum game: en.wikipedia.org/wiki/Minimax_theorem $\endgroup$ Aug 21, 2021 at 20:28
  • 1
    $\begingroup$ Maybe there is no deterministic answer: blogs.cornell.edu/info2040/2015/10/19/… But a probabilistic approximation is good enough for me. Probably I can start from a random feasible point and then alternate the maximization and minimization steps. Stop when I reach a cycle of solutions. Then try another random initial point again to find all cycles of solutions. $\endgroup$ Aug 21, 2021 at 20:58
  • $\begingroup$ @QuriousCube There is no feasible point. Please see my answer. $\endgroup$
    – rasul
    Aug 22, 2021 at 9:33
  • $\begingroup$ That is nice. That gets rid of one branch of the search tree. $\endgroup$ Aug 22, 2021 at 16:42

1 Answer 1

4
$\begingroup$

The problem is infeasible:

$(c_1,c_2) \Rightarrow x_1=1$

$(c_3,c_4) \Rightarrow x_2+x_3=2$

$(c_1,c_2,c_7) \Rightarrow x_4 + x_5 \le 2$

$(c_5,c_6) \Rightarrow -(x_2+x_3)+0.4(x_4+x_5) \ge 2 \text{ and so } (c_3,c_4,c_5,c_6)\Rightarrow x_4 + x_5 \ge 10$

The last two lines are not consistent. Note that we also obtain a conflict with $(c_8,c_9)$:

$(c_8,c_9) \Rightarrow -0.6(x_2+x_3)+(x_4+x_5) \ge 1.2 \text{ and so } (c_3,c_4,c_8,c_9)\Rightarrow x_4 + x_5 \ge 2.4$

$\endgroup$
3
  • $\begingroup$ How can a computer know that the problem is infeasible? $\endgroup$ Aug 22, 2021 at 16:50
  • $\begingroup$ Never mind. Just have add slack and surplus variables and then solve the system of equality $\endgroup$ Aug 22, 2021 at 16:53
  • $\begingroup$ @QuriousCube Once the problem is infeasible, you can use a feature of linear solvers called conflict refiner that gives you a minimal set of conflicting constraints. Gurobi calls this minimal set an Irreducible Inconsistent Subsystem (IIS). I haven't used a solver for this problem though. I started to characterize the basic feasible solutions of the minimization part (which only has two variables $x_2$ and $x_3$) to subsequently solve the original problem, and then realized that it is infeasible. $\endgroup$
    – rasul
    Aug 22, 2021 at 17:30

Your Answer

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

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