Facility location problem with a cost function

Question

I'm struggling with a facility location problem.

In its original form the problem is quite straightforward: Given a matrix of distances between cities, I have to pick a minimal number of centers from them and create districts, such that no city in a district is farther from the center than a predefined distance parameter. This is a set covering problem that can be formulated as a binary integer program which I can solve with MATLAB's bintprog(). The solution vector gives me the list of cities that are selected as centers, after which I can establish districts by assigning each city to the closest center, and that's OK.

But I would also like to solve a specialized version of the problem, and this is where it gets ugly and I get stuck:

Let's assume we also know the population of each city and want to minimize the amount of people who have to commute to the district center, and also the distance they have to do. So we would like to prefer solutions where the cost

$$ C =\sum_{v \in V}P_v \times d_{vc} $$

is minimal ($v \in V$ are the cities in the district, $P_v$ is the population of $v$, and $d_{vc}$ is the distance to the center).

My problem is that I cannot think of a way to incorporate these constraints into the binary integer program, because computing these costs require the districts to be already established, which right now only happens after bintprog() has returned.

I suspect this problem might not even be formulated as a linear program at all, but I'm yet to find another way to solve it, so any help would be much appreciated. Thanks.

Answer 1

The problem you're asking to solve is a variant of the $k$-median problem on a metric space. You haven't mentioned anything about the various sizes involved, but as a formal matter, there are only $n$ choices for the magic number $k$ (the number of centers), and so after "guessing" the right value of $k$, you can run any of the standard approximation algorithms for $k$-median in graphs (your graph is a complete graph). In particular, one such is the method by Jain and Vazirani.

There's an older technique by Lin and Vitter that says that if you're willing to expand the number of centers by a tiny amount, you can get a pretty good approximation to the cost (w.r.t optimal centers).

Answer 2

Okay, I'll bite. Isn't your problem a special case of (non-metric) $k$-medians?

Given a budget $k$ for the number of centers you want to open, and a bound $D$ on the maximum allowed distance on any city $v$ to its assigned center $c$, define $d'_{vc}$ to be $\infty$ if $d_{vc}>D$ and $P_v d_{vc}$ otherwise. Then your problem is modeled by the standard integer linear program for $k$-medians with (non-metric) distances $d'_{vc}$.

$~\displaystyle \min \sum_{vc} d'_{vc} X_{vc}$ subject to

1. Each city is assigned to some center: for each $v$, $\sum_c X_{vc} = 1$.

2. Any assigned center must be open: for each $c$ and $v$, $X_{vc} \le Y_c$.

3. Exactly $k$ centers are opened: $\sum_{c} Y_c = k$.

4. All variables non-negative.

For non-metric $k$-medians, I think the best poly-time approximation known is here, Theorem 5, which gives a solution that opens $O(k\log n)$ centers and achieves cost at most the optimum cost possible with $k$ centers.

Or, if you'd rather relax the distance constraint (say, if your $d_{vc}$ is metric, and your approximate solution can only use $k$ centers but can assign cities to centers that are $2D$ away), you might be able to get a constant-factor approximation to OPT (where OPT has to assign cities to centers that are at most $D$ away). I'm not sure for this particular problem, but I know there are existing results of that kind for problems similar to that, such as Jain and Vazirani's 6-approximation for metric k-medians and 2-approximation algorithms for metric k-center.

Answer 3

I don't think the matrix is necessarily helping you. Have you looked at $k$-mean. For a scattered collection of points, $k$-mean divides those points into $k$ collections around center points.

You may want to evaluate your results with different values of $k$ to determine what is most cost effective. However, I once saw an implementation of a $k$-mean in conjunction with a self-organizing map. I believe the self-organizing map was used to divide a collection of points into various regions to determine an optimum $k$. Then, $k$-mean was used to find the center of each collection.