# Is there an optimization algorithm that could help match the maximum number clients to servers with constraints?

How do you go about solving the following problem that tries to match the greatest number of clients with servers with constraints? I'm trying to identify an algorithm or simulation that could help me solve this problem as optimally as possible.

Assume you are given a 2d map of servers and clients randomly scattered. Each server can handle a certain radius of clients but never two clients that are near each other (this is the constraint). While it makes sense for a server to handle all the clients near it, some clients may need to be handled by another server nearby. Picking which of those clients should be handled by another server (potentially farther but still in reach) such that the maximum number of clients can be handled is the objective.

Not all clients necessarily can be handled, but the problem should be able to match the most number of clients with servers possible, and the constraint must be upheld.

• I think linear programming should do pretty well in this case: you can introduce variable $x_{ps}$ for each person $p$ and reachable server $s$. You want to maximize $\sum_{ps}x_{ps}$. The constraints are $x_{ps} \in [0,1]$ and $x_{p_1s}+x_{p_1s} \le 1$ if $p_1$ and $p_2$ are close. This is not exact reformulation (you need $x_{ps} \in \{0,1\}$), but I expect solutions to be close to integral (or can be converted to integral). If you have more information about distribution of people (e.g. how likely two persons to be nearby and whether they form clusters), simpler solutions are possible. – Dmitry Feb 25 at 6:30
• First, formalise and name near each other - $l$ - and in reach - $u$. Go for low-hanging fruit first: weed out clients too far from any server - how about keeping for every client the number of servers in reach? (Weeding out server is more difficult - jot down why/how.) What are difficult cases, what about a line of client positions at a distance of $\frac{2l}{5}$? – greybeard Feb 25 at 6:35
• I'm confused by "never two clients that are near each other" and "makes sense to handle all the clients near it". If a server handles all clients near it, then presumably it will be handling clients that are near each other. So I'm lost. – D.W. Feb 25 at 7:18
• – D.W. Feb 25 at 8:05