3
$\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?

Improve this question
$\endgroup$
4
  • $\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, 2011 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, 2011 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, 2011 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, 2011 at 16:41

1 Answer 1

Reset to default
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].

Improve this answer
$\endgroup$
3
  • $\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, 2011 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, 2011 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, 2011 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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