Why are integer minimax problems hard?

Question

Problems that have a minimax-type structure are notoriously hard to solve. For example, the $p$-median problem from facility location (choose $p$ facilities to minimize demand-weighted distance to customers) does not have a minimax structure: $$\begin{alignat}{2} \text{minimize} \quad & \sum_i \sum_j h_id_{ij}y_{ij} \\ \text{subject to} \quad & \sum_j y_{ij} = 1 &\quad& \forall i \\ & y_{ij} \le x_j && \forall i, j \\ & \sum_j x_j = p \\ & x_j, y_{ij} \in \{0,1\} && \forall i, j \end{alignat}$$ ($h_i$ = demand of customer $i$, $d_{ij}$ = distance from $i$ to $j$, $x_j$ = 1 if we open facility $j$, $y_{ij}$ = 1 if we assign $i$ to $j$.) Its cousin, the $p$-center problem (minimize the maximum distance from a customer to its assigned facility), does have a minimax structure: $$\begin{alignat}{2} \text{minimize} \quad & u \\ \text{subject to} \quad & \sum_j y_{ij} = 1 &\quad& \forall i \\ & y_{ij} \le x_j && \forall i, j \\ & \sum_j x_j = p \\ & \sum_j d_{ij}y_{ij} \le u && \forall i \\ & x_j, y_{ij} \in \{0,1\} && \forall i, j \end{alignat}$$ ($u$ = maximum distance to assigned facility, among all customers.)

I solved a benchmark 88-node instance of the $p$-median problem with $p=6$ using CPLEX and it took 0.7 seconds. I solved the same instance of the $p$-center problem and it took CPLEX 1,607 seconds.

Similar effects happen, e.g., for stochastic facility location (minimize expected cost) vs. robust facility location (minimize maximum cost).

I always tell my students, "these minimax-type problems are just really hard for solvers to solve," but I don't have a good explanation for why. (I know their LP relaxations are weak, but again I don't know why this tends to happen.)

So, why are minimax problems harder to solve, computationally?

And, are there any types of automatically generated cuts that one can turn on in commercial solvers that tend to help with minimax problems?

Answer 1

I can see two reasons why branch-and-bound based solvers can have a hard time solving these problems:

• the linear relaxation may be bad (as stated above);

• these models have typically (exponentially) many optimal solutions, since the cost only depends on a single variable $y_{ij}$. Thus, you can move one customer to many centers without changing the cost of a solution.

For p-center, models that distribute the cost over several variables seem to be much more MIP-solver friendly. At least their linear relaxations are better (see for example Elloumi et al., 2004 ).

Answer 2

This is going to be a hand-waving argument: perhaps this has been formalized in the literature someplace.

I think the issue is that the linear relaxation is in some sense more compatible with the p-median objective than the p-center problem. Consider the following example (circles are customers; stars are facilities)

For the left hand customers, the distance to the closest facility is 1; for the right hand customer, the closest facility (also on the right) is 3; the distance between the left column and the right column is 6.

For p-median, everything gets assigned to their closest facility. This is true for the linear relaxation as well.

If you try to assign the right-hand customer to the left-hand facilities, it will cost 6 no matter how you assign it: it is cheaper to assign it to the right-hand facility at cost 3. Assigning fractional solutions doesn't "cheat": a good assignment will be pushed toward value 1.

For p-center, though, there is an advantage in the linear relaxation to fractionally assign things. In our example, the best integer assignment for the right-hand-side customer is still to its closest facility at cost 3. But fractionally, there is a value to assign things to the left hand side:

If you put weight 1/3 on each of the dotted lines, then the p-center cost goes down to 2. In fact, the optimal thing to do is to is to assign weight .2 to each of the dotted lines, leaving .4 for the right hand facility, for a cost of 1.2.

Given the nasty fractional solution in this almost trivial example, it is not surprising that branch and bound has to work very hard to get to an integer solution.

This leads to the possibly-useful but not-tremendously-insightful cut of $u \ge d^*$ where $d^*$ is the largest minimum distance among all customers to its closest facility.

Answer 3

I will give you a little more insight based on my latest experience solving minimax (or maximin) integer programs. Sorry I will be a bit self-citing here.

Indeed, the main reason that can explain the poor behavior of commercial solvers for solving those types of problems is the strong dependence on a single (or a very few) variable for the solution. In p-centre problems, it is the distance from the furthest node to its closest center. If you think a little, you will realize that a large number of the nodes are only noise and do not play any role in the optimization. Thus, the linear relaxation tends to behave poorly because the cost will tend to be split among several variables. In addition, the number of symmetries can be unreasonably large (for a given centre, there might be exponentially many possible assignments with the same cost), which is deadly for branch-and-bound.

Now, I will argue that your point is not TOTALLY true. While plugging a minimax integer model into CPLEX or Gurobi can be a bad idea, there has been some recent research aiming at exploiting the issues described in the paragraph above and exploit them. Think of the p-centre problem. If you KNOW that a lot of points are only noise, why consider them? Chen & Chen (2009) showed that a decremental relaxation algorithm can be used to discard points that are deemed noisy. One then can solve the noise-free problem (small) and later assess whether this partial solution can be extended to a solution of the whole problem, which can be done very efficiently. Contardo, Iori and Kramer (2019, C&OR) showed that, when implemented correctly, and with the addition of a few acceleration mechanisms, problems containing up to 1M points can be solved to proven optimality.

The minimax diameter clustering problem (MMDCP) has a similar structure. In the MMDCP, one is given a set of n points, a dissimilarity matrix D and an integer k. One seeks to determine k clusters in such a way that the maximum distance between any two points within the same cluster, is minimized. This problem is NP-hard and problems with only a few thousand nodes could be handled by commercial solvers. Aloise and Contardo (2018, JOGO) showed that indeed a similar mechanism to the one used for the p-centre problem can be devised to sample points in an iterative manner. Problems with up to 600k can be solved to proven optimality.

A few months ago I came up with a similar mechanism for discrete p-dispersion problems (pDP). In the pDP, one is given n points, a dissimilarity matrix D and an integer p. The objective is to select p points such that the minimum distance between any pair of selected points is maximized. I devised a clustering mechanism to reduce this problem to a series of smaller pDPs. Problems containing up to 100k nodes can be solved to proven optimality.

So here is my final opinion: If ever faced to a large-scale minimax (or maximin) integer problem, spend your time thinking on how to reduce that problem to the solution of smaller problems, so as to reduce the noise that makes you problem hard and with a high degree of symmetry. Then devise an algorithm to exploit those observations in an iterative manner.

References

• Chen & Chen (2009), New relaxation-based algorithms for the optimal solution of the continuous and discrete p-center problems. C&OR. Can be downloaded from R Chen's website for free

• Aloise & Contardo (2018), A sampling-based exact algorithm for the solution of the minimax diameter clustering problem, JOGO

• Contardo, Iori & Kramer (2019), A scalable exact algorithm for the vertex p-center problem, C&OR
• Contardo (2019), Decremental clustering for the solution of p-dispersion problems to proven optimality. Cahier du GERAD G-2019-22

Answer 4

You may find this paper (On the Complexity of Min-Max Optimization Problems and their Approximation interesting.

Also, only looking at the $p$-median and $p$-center examples you shared, I can say that the constraints of $p$-center problem (or its space), is equivalent to solving a $p$-median problem where $h_i = 1$. So, $p$-center is solving a series of $p$-median problems. Hopefully, this is not a wrong interpretation!