Minmax combinatorial optimization with target set size constraint

Question

I have a combinatorial optimization problem whose objective is in the "min-max" form.

Suppose that there is a row stochastic matrix $P=[p_1^T,\cdots,p_n^T]^T\in\mathbb{R}^{n\times n}$ whose elements are all positive, and $p_i$ is the $i$-th row of the matrix $P$ that sum up to 1. There is also a given vector $x\in\mathbb{R}^{n\times n}$ whose entry are all in range $(0, 1)$. The problem can be formulated as follow:

Choose $k$ of $x$'s entry whose indexes to form a set $U$. Set the selected entries of $x$ to $0$, and obtain a new vector $\tilde{x}$. We want to $$ \begin{aligned} \min_{U} \max_i~ p_i^T \tilde{x}\\ s.t.~ \vert U\vert = k \end{aligned} $$ That is, finding $k$ of $x$'s entries and set them to $0$, so that the maximum of $P\tilde{x}$ is minimized.

I find that there is not too much efficient algorithm for such "min-max" type of combinatorial problem.

What I have done

• Convex Relax.I first transform the above problem into the following 0-1 integer programming $$ \begin{aligned} \min_y \max_i \big[P\cdot \text{Diag}(x) \cdot y\big]_i\\ s.t.~ 1^T y = n-k\\ \quad y_i = \{0, 1\}. \end{aligned} $$ Then, I relax the last 0-1 constraints into $0\le y_i \le 1$. The relaxed problem is actually a linear programming, and thus can be solved efficiently. After solving the relaxed LP, I directly set the largest $n-k$ of $y^*_i$ to 1 and other entries to 0.
• Gurobi 01P. I use Gurobi to solve the transformed 0-1 problem with branch-and-bound algorithm (possibly I think), and this yields the optimal solution to the original problem.
• Greedy MinMax. I use the greedy algorithm as in Kempe'03. That is, pick the selected entry one by one, so that each selected can myopically minimize the objective at that round. Typically, if the objective satisfies "super-modularity" and "monotone", then this greedy method yields an $(1-1/e)$ sub-optimality. However, in our case, the objective does not satisfy "super-modularity", and the sub-optimality is not guaranteed.
• Greedy Sum. I tried to modified the objective function into $|P\tilde{x}|_1$. It is easy to solve such combinatorial problem by first obtaining the indexes of the $k$ largest columns sum of $P~\text{Diag}{(x)}$, and then setting these indexes of $x$ to zero.

I run 50 repeat experiments and obtain the following results:

I have the following questions:

1. Is there some studies on how to solve such type of min-max combinatorial problem, so that the performance is guaranteed.

2. The relaxed method seems to perform well, but I am still wondering the suboptimality of this method.

3. Is there better relax method?

4. Can "Branch-and-bound" method be optimized according to the min-max objective?

5. What is the optimality of the "Greedy Min-Max" method?

I would thank anyone who have read here first, because this post may be a little longer as I want to make everything clear. Any advice, clues and discussions are welcomed. Thanks ahead!

Answer 1

You might consider bisection search for the optimal objective value $z^*$. Here, $0$ is a lower bound, and any set $U$ provides an upper bound. At each step, solve a feasibility problem for the current trial value $\hat{z}$, with linear constraints that enforce $p_i^T \tilde{x}\le \hat{z}$ for all $i$. If the problem is feasible, update the upper bound of the search interval to $\hat{z}$. If the problem is infeasible, update the lower bound of the search interval to $\hat{z}$. Continue until the search interval is sufficiently small.