19 votes

Why are integer minimax problems hard?

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-...
user avatar
19 votes
Accepted

Why are integer minimax problems hard?

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) ...
user avatar
11 votes
Accepted

Symmetric undirected $p$-median instance with fractional LP solution?

I think I've found an instance with four nodes and $p = 2$ via brute force (a lot of randomized instances). I've attached my Python script as well. I relaxed the Daskin and Maass (2015) formulation ...
user avatar
  • 1,759
11 votes

Why are integer minimax problems hard?

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 ...
user avatar
6 votes

Why are integer minimax problems hard?

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 ...
user avatar
  • 5,651

Only top scored, non community-wiki answers of a minimum length are eligible