<p>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 <a href="http://dl.acm.org/citation.cfm?id=375845" rel="nofollow">Jain and Vazirani</a>. </p>

<p>There's an older technique by <a href="http://dl.acm.org/citation.cfm?id=129787&amp;CFID=107848450&amp;CFTOKEN=31892640" rel="nofollow">Lin and Vitter</a> 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). </p>

CC BY-SA 3.0
2012-11-03T04:57:36.937Z
FWIW, we've improved Lin and Vitter's result, first
[here, Corollary 6.1](http://www.cs.ucr.edu/~neal/Papers/SODA_2000_86.pdf)
and then [here, Theorem 5](http://www.cs.ucr.edu/~neal/Papers/algorithmica_2008_50_4_455.pdf).
The latter result says that with $O(k \log m)$ medians you can 
achieve the same assignment cost as OPT does with $k$ medians.
Neal Young
CC BY-SA 3.0
2012-11-06T03:58:55.097Z
Maybe you should post a new answer :)
Suresh Venkat
CC BY-SA 3.0
2012-08-25T00:31:53.853Z
2012-08-25T00:31:53.853Z
Suresh Venkat
<p>Okay, I'll bite.  Isn't your problem a special case of (non-metric) $k$-medians?</p>

<p>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}&gt;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}$.</p>

<p>$~\displaystyle \min \sum_{vc} d'_{vc} X_{vc}$ subject to</p>

<ol>
<li><p>Each city is assigned to some center: for each $v$, $\sum_c X_{vc} = 1$.  </p></li>
<li><p>Any assigned center must be open: for each $c$ and $v$, $X_{vc} \le Y_c$. </p></li>
<li><p>Exactly $k$ centers are opened: $\sum_{c} Y_c = k$.</p></li>
<li><p>All variables non-negative.</p></li>
</ol>

<p>For non-metric $k$-medians, I think the best poly-time approximation known is <a href="http://www.cs.ucr.edu/~neal/Papers/algorithmica_2008_50_4_455.pdf" rel="nofollow">here, Theorem 5</a>, which gives a solution that opens $O(k\log n)$ centers and achieves cost at most the optimum cost possible with $k$ centers.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Metric_k-center" rel="nofollow">metric k-center</a>.</p>

CC BY-SA 3.0
2012-11-06T06:26:28.117Z
2012-11-06T07:00:57.007Z
2012-11-06T07:00:57.007Z
Neal Young
<p>I don't think the matrix is necessarily helping you. Have you looked at <a href="http://en.wikipedia.org/wiki/K-means_clustering" rel="nofollow">$k$-mean</a>.  For a scattered collection of points, $k$-mean divides those points into $k$ collections around center points. </p>

<p>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 <a href="http://en.wikipedia.org/wiki/Self-organizing_map" rel="nofollow">self-organizing map</a>. 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. </p>

CC BY-SA 3.0
2012-08-24T15:50:20.427Z
2012-08-24T15:50:20.427Z
Josh C.
<p>I'm struggling with a facility location problem.</p>

<p>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 <code>bintprog()</code>. 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.</p>

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

<p>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</p>

<p>$$
C =\sum_{v \in V}P_v \times d_{vc}
$$</p>

<p>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).</p>

<p>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 <em>after</em> <code>bintprog()</code> has returned. </p>

<p>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.</p>

CC BY-SA 3.0
2012-08-16T22:13:57.620Z
dont see how this reduces to a set covering problem unless you enumerate all possibilities somehow which seems large. can you sketch out how it reduces to a set covering? anyway looking at it there is probably more than one way to solve this problem or optimize in practice....
vzn
<cg.comp-geom><optimization><application-of-theory><set-cover><integer-programming>
Facility location problem with a cost function
brncsk
# Facility location problem with a cost function

(Asked by: username_0 on 2012-08-16)

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.

**Tags:** cg.comp-geom, optimization, application-of-theory, set-cover, integer-programming
> **Comments:**
> **username_1**: dont see how this reduces to a set covering problem unless you enumerate all possibilities somehow which seems large. can you sketch out how it reduces to a set covering? anyway looking at it there is probably more than one way to solve this problem or optimize in practice....  

---

## 3 answers

### Answer by username_2 on 2012-08-25. Score: 3

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](http://dl.acm.org/citation.cfm?id=375845).

There's an older technique by [Lin and Vitter](http://dl.acm.org/citation.cfm?id=129787&CFID=107848450&CFTOKEN=31892640) 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).

> **Comments:**
> **username_3**: FWIW, we've improved Lin and Vitter's result, first [here, Corollary 6.1](http://www.cs.ucr.edu/~neal/Papers/SODA_2000_86.pdf) and then [here, Theorem 5](http://www.cs.ucr.edu/~neal/Papers/algorithmica_2008_50_4_455.pdf). The latter result says that with $O(k \log m)$ medians you can  achieve the same assignment cost as OPT does with $k$ medians.  
> **username_2**: Maybe you should post a new answer :)  

---

### Answer by username_3 on 2012-11-06. Score: 1

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](http://www.cs.ucr.edu/~neal/Papers/algorithmica_2008_50_4_455.pdf), 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](http://en.wikipedia.org/wiki/Metric_k-center).


---

### Answer by username_4 on 2012-08-24. Score: 0

I don't think the matrix is necessarily helping you. Have you looked at [$k$-mean](http://en.wikipedia.org/wiki/K-means_clustering). 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](http://en.wikipedia.org/wiki/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.


---

