2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – bbejot May 17 '11 at 17:32
  • $\begingroup$ 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. $\endgroup$ – Haffi112 May 17 '11 at 18:06
  • $\begingroup$ 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. $\endgroup$ – Yoshio Okamoto May 18 '11 at 9:37
  • $\begingroup$ 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. $\endgroup$ – Haffi112 May 18 '11 at 16:41
4
$\begingroup$

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].

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Haffi112 May 20 '11 at 10:48
  • $\begingroup$ @Haffi112: You may try to search by "clustering", which has a similar flavor with facility location. $\endgroup$ – Yoshio Okamoto May 20 '11 at 12:11
  • $\begingroup$ @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. $\endgroup$ – James King May 21 '11 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.