# Facility Location problem, multiple facilities with no specific locations

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?

• 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 May 17 '11 at 17:32
• 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 May 17 '11 at 18:06
• 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 May 18 '11 at 9:37
• 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 May 18 '11 at 16:41