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-...
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) ...
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 ...
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 ...
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
facility-location × 2p-median × 2
mixed-integer-programming × 1
lp-relaxation × 1
minimax × 1