The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [facility-location]

For questions related to optimization problems for choosing the optimal locations of facilities such as warehouses, factories, fire stations, etc.

Filter by
Sorted by
Tagged with
9
votes
1answer
62 views

Using Spatial Multi Criteria Analysis for simultaneously locating various facilities?

Is it possible to use SMCA (Spatial Multi Criteria Analysis) for determining simultaneously where to locate various facilities? Suppose, for example, I'm planing to build a new city and everything ...
15
votes
1answer
147 views

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

The $p$-median problem is NP-hard, so its LP relaxation does not naturally have all-integer solutions. However, it very often does; in fact, it can be hard to find an instance for which the LP ...
8
votes
2answers
270 views

Linear facility location problem for large size problems (police station)

Considering a set of $m$ existing weighted demand points (very large) and $n$ different-sized facilities, what is the best approach for locating new facilities to maximise coverage? I have used the ...
11
votes
2answers
140 views

partitioning hub assignment models

When solving large-scale hub assignment models (1000+ candidate hubs and 1000+ demand nodes), it is possible that parts of a cost matrix are not connected to one another. A typical workflow would be: ...
10
votes
1answer
101 views

Algorithmic gap for Hochbaum's (greedy) algorithm for (metric) uncapacitated facility location

In Jain et al. (2003)1, at the bottom of page 801, they construct an instance of (metric) uncapacitated facility location for which they claim the greedy (Hochbaum's) algorithm has gap $\Omega\left(\...
22
votes
4answers
235 views

Why are integer minimax problems hard?

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 ...
9
votes
2answers
129 views

How to quantify the “griddiness” of a set of points?

We're working on a facility location problem in which it is desirable for the facilities to be laid out as close as possible to a grid. In our problem, a lattice is overlaid on the region, and the ...