# Minmax combinatorial optimization with target set size constraint

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!

• Interesting to see Gurobi achieve best results... Apr 23, 2021 at 17:05
• @gt6989b I think that makes sense because it uses algorithm like branch-and-bound, so it should be better than "convex relax" method (because this relaxation is like the first step of "branch-and-bound"). However, it really takes a long time for branch-and-bound, when $n$ is rather large. Apr 24, 2021 at 1:26
• True. Gurobi (as any other decent solver) should also use a bunch of heuristics that help speed up the trimming of the B&B tree. Apr 25, 2021 at 15:02
• I see, seems like the heuristics Gurobi uses is better than the method I designed. Apr 26, 2021 at 2:37
• Some solvers, including Gurobi, allow you to embed your own specialized heuristics in the branch-and-bound search via a callback function. Most solvers also allow you to supply a starting solution that can help speed up the search, even without using callbacks. Apr 26, 2021 at 2:56

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.
• This bisection search method seems to be efficient. But, I have a little question about solving "feasibility problem". Is this feasibility problem with $x_i = {0, 1}$ constraint or $0\le x_i \le 1$ constraint? If it is the former one, the feasibility problem seems to be also hard to solve? Apr 26, 2021 at 15:54
• The feasibility problem has $x_i \in\{0,1\}$, and yes it might still be difficult. The hope is that it is sufficiently easier than the optimality problem that you can afford to solve the feasibility problem several times. Note also that when you find a feasible solution you can update the upper bound to the correct objective value, which might be smaller than the current target value $\hat{z}$. Apr 26, 2021 at 16:08