<p>What you're talking about is, I believe, called the Capacitated Facility Location Problem.  Searching for that should give you plenty of papers to read.  It appears the problem is NP-hard, but in Euclidean space a simple search procedure gives you a 6-approximation <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.1704&amp;rep=rep1&amp;type=pdf" rel="nofollow">[PDF]</a>.</p>

CC BY-SA 3.0
2011-05-20T10:48:28.873Z
Thank you for this suggestion. In all the facility location problem articles I've encountered so far the possible locations of the facilities are predetermined. Is it not possible to let the facility locations be continuous (i.e. not a set of possible positions)? It would be like the fermat weber problem but with many points instead of one.
Haffi112
CC BY-SA 3.0
2011-05-20T12:11:00.073Z
@Haffi112: You may try to search by "clustering", which has a similar flavor with facility location.
Yoshio Okamoto
CC BY-SA 3.0
2011-05-21T14:22:14.537Z
@Haffi112 In that case I think what you're looking for would be called the Capacitated k-Means Problem.  There doesn't seem to be much out there on this.  Your idea of using a modified k-Means method seems very appropriate.
James King
CC BY-SA 3.0
2011-05-19T10:23:12.377Z
2011-05-19T10:23:12.377Z
James King
<p>My problem is as follows:</p>

<p>I have $n$ customers, each with a predetermined location in the plane, i.e. $(x,y)\in\mathbb{R}^2$. I have $k$ facilities I want to distribute such that each one of them can serve up to $m$ customers.</p>

<p>I'm struggling with how I should formulate the cost function so I can solve it with non-linear programming (I'm going to start off by using <a href="http://abel.ee.ucla.edu/cvxopt/" rel="nofollow">http://abel.ee.ucla.edu/cvxopt/</a>).</p>

<p>I have also though about just using a modified $k$-means method if everything else fails but I really want to try the other option first.</p>

<p><strong>Edit:</strong> If the task above is too hard I could consider skipping the requirement that each facility can only serve $m$ customers and that I only have to distribute the facilities to minimize distance to their customers.</p>

<p><strong>Edit 2 (<em>real scenario to explain the reason for this formulation</em>):</strong> A company has location information for all their customers, the company is going to open $k$ facilities (e.g. shops). Each facility can serve up to $m$ customers, how should we place the facilities such that the total distance to the customers they serve is minimized?</p>

CC BY-SA 3.0
2011-05-17T17:32:57.257Z
Do you mean to say that you need to place the $k$ facilities such that each facility has at most $m$ customers for which that facility is the closest?
bbejot
CC BY-SA 3.0
2011-05-17T18:06:22.410Z
Either that or that each facility has up to $m$ customers which are not necessarily the closest customers. One possibility would be to let each facility have a binary vector which denotes which customer he serves but that would change the problem to an integer-optimization problem.
Haffi112
CC BY-SA 3.0
2011-05-18T09:37:17.173Z
You need a clarification on what you mean by "solve" and "non-linear".  On "non-linear", for example, a binary decision can be represented by a non-linear equality: $x\in\{0,1\}$ if and only if $x(x-1)=0$. On "solve", for example, facility location problems are typically NP-hard.  So, solving to optimality in polynomial time might not be possible.
Yoshio Okamoto
CC BY-SA 3.0
2011-05-18T16:41:00.067Z
By non-linear I mean I want to be able to use a non-linear cost function which I can find a good approximate solution by using non-linear optimization methods, e.g. gradient descent methods. I'm going to change the question a little bit and give a real world example.
Haffi112
<ds.algorithms>
Facility Location problem, multiple facilities with no specific locations
Haffi112
# Facility Location problem, multiple facilities with no specific locations

(Asked by: username_0 on 2011-05-17)

My problem is as follows:

I have $n$ customers, each with a predetermined location in the plane, i.e. $(x,y)\in\mathbb{R}^2$. I have $k$ facilities I want to distribute such that each one of them can serve up to $m$ customers.

I'm struggling with how I should formulate the cost function so I can solve it with non-linear programming (I'm going to start off by using <http://abel.ee.ucla.edu/cvxopt/>).

I have also though about just using a modified $k$-means method if everything else fails but I really want to try the other option first.

**Edit:** If the task above is too hard I could consider skipping the requirement that each facility can only serve $m$ customers and that I only have to distribute the facilities to minimize distance to their customers.

**Edit 2 (*real scenario to explain the reason for this formulation*):** A company has location information for all their customers, the company is going to open $k$ facilities (e.g. shops). Each facility can serve up to $m$ customers, how should we place the facilities such that the total distance to the customers they serve is minimized?

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: Do you mean to say that you need to place the $k$ facilities such that each facility has at most $m$ customers for which that facility is the closest?  
> **username_0**: Either that or that each facility has up to $m$ customers which are not necessarily the closest customers. One possibility would be to let each facility have a binary vector which denotes which customer he serves but that would change the problem to an integer-optimization problem.  
> **username_2**: You need a clarification on what you mean by "solve" and "non-linear".  On "non-linear", for example, a binary decision can be represented by a non-linear equality: $x\in\{0,1\}$ if and only if $x(x-1)=0$. On "solve", for example, facility location problems are typically NP-hard.  So, solving to optimality in polynomial time might not be possible.  
> **username_0**: By non-linear I mean I want to be able to use a non-linear cost function which I can find a good approximate solution by using non-linear optimization methods, e.g. gradient descent methods. I'm going to change the question a little bit and give a real world example.  

---

## 1 answers

### Answer by username_3 on 2011-05-19. Score: 4 | Accepted answer

What you're talking about is, I believe, called the Capacitated Facility Location Problem. Searching for that should give you plenty of papers to read. It appears the problem is NP-hard, but in Euclidean space a simple search procedure gives you a 6-approximation [[PDF]](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.1704&rep=rep1&type=pdf).

> **Comments:**
> **username_0**: Thank you for this suggestion. In all the facility location problem articles I've encountered so far the possible locations of the facilities are predetermined. Is it not possible to let the facility locations be continuous (i.e. not a set of possible positions)? It would be like the fermat weber problem but with many points instead of one.  
> **username_2**: @username_0: You may try to search by "clustering", which has a similar flavor with facility location.  
> **username_3**: @username_0 In that case I think what you're looking for would be called the Capacitated k-Means Problem.  There doesn't seem to be much out there on this.  Your idea of using a modified k-Means method seems very appropriate.  

---

