How Many Servers Do You Need and Where?
When building distributed systems or cloud infrastructure, one of the most fundamental planning questions is: Given a set of demand locations and potential server sites, how many servers should be installed, and where? This is the Server Placement (Facility Location) Problem — a classic combinatorial optimization problem that can be solved elegantly with Integer Linear Programming.
Problem Formulation
We have a set of candidate server locations and a set of client nodes (offices, data centers, end-users). Each candidate site has a fixed installation cost and a capacity. Each client has a demand. We want to minimize total cost — installation plus service (routing/bandwidth) cost — while ensuring all demand is met.
Sets:
$$I = {1, 2, \ldots, m}$$ — set of candidate server sites
$$J = {1, 2, \ldots, n}$$ — set of client nodes
Parameters:
$$f_i$$ — fixed installation cost at site $i$
$$c_{ij}$$ — unit service cost from server $i$ to client $j$
$$d_j$$ — demand of client $j$
$$s_i$$ — capacity of server at site $i$
Decision Variables:
$$x_i \in {0, 1}$$ — 1 if a server is installed at site $i$, 0 otherwise
$$y_{ij} \geq 0$$ — fraction of client $j$’s demand served by server $i$
Objective — minimize total cost:
$$\min \sum_{i \in I} f_i x_i + \sum_{i \in I} \sum_{j \in J} c_{ij} d_j y_{ij}$$
Subject to:
All demand of each client must be fully served:
$$\sum_{i \in I} y_{ij} = 1 \quad \forall j \in J$$
A client can only be served from an open server:
$$y_{ij} \leq x_i \quad \forall i \in I,\ \forall j \in J$$
Capacity constraint at each server:
$$\sum_{j \in J} d_j y_{ij} \leq s_i x_i \quad \forall i \in I$$
Variable domains:
$$x_i \in {0, 1},\quad y_{ij} \geq 0$$
Concrete Example
We set up a scenario with 8 candidate server sites and 15 client nodes scattered across a 2D map (coordinates in km). The clients have varying demands; the servers have different installation costs and capacities. Service cost is proportional to Euclidean distance.
| Site | X (km) | Y (km) | Fixed Cost (¥) | Capacity |
|---|---|---|---|---|
| S0 | 10 | 80 | 5,000 | 150 |
| S1 | 30 | 60 | 4,500 | 130 |
| S2 | 55 | 85 | 6,000 | 200 |
| S3 | 75 | 70 | 4,000 | 120 |
| S4 | 20 | 30 | 5,500 | 160 |
| S5 | 50 | 40 | 4,800 | 180 |
| S6 | 80 | 20 | 5,200 | 140 |
| S7 | 65 | 55 | 3,800 | 110 |
| Client | X (km) | Y (km) | Demand |
|---|---|---|---|
| C0 | 5 | 90 | 20 |
| C1 | 15 | 75 | 35 |
| C2 | 25 | 85 | 25 |
| C3 | 40 | 70 | 40 |
| C4 | 60 | 90 | 30 |
| C5 | 80 | 85 | 45 |
| C6 | 10 | 50 | 28 |
| C7 | 35 | 50 | 33 |
| C8 | 55 | 60 | 38 |
| C9 | 75 | 50 | 22 |
| C10 | 90 | 60 | 27 |
| C11 | 20 | 15 | 31 |
| C12 | 45 | 20 | 36 |
| C13 | 70 | 10 | 24 |
| C14 | 90 | 30 | 29 |
The service cost matrix is defined as:
$$c_{ij} = \text{rate} \times \sqrt{(sx_i - cx_j)^2 + (sy_i - cy_j)^2}$$
with a unit rate of ¥10 per km per unit demand.
Python Source Code
1 | # ============================================================ |
Code Walkthrough
Section 0 — Setup
PuLP is installed quietly. numpy handles all numerical arrays; matplotlib with mpl_toolkits.mplot3d provides all plotting including the 3D views. warnings.filterwarnings("ignore") suppresses CBC solver output.
Section 1 — Problem Data
Server sites are stored as tuples (x_km, y_km, fixed_cost, capacity). Eight candidate sites are spread across a 100 × 100 km map with fixed installation costs between ¥3,800 and ¥6,000 and capacities from 110 to 200 demand units.
Client nodes are tuples (x_km, y_km, demand). Fifteen clients with demands ranging from 20 to 45 units are distributed across the same region.
The service cost matrix is built as:
$$c_{ij} = \text{unit_rate} \times \sqrt{(sx_i - cx_j)^2 + (sy_i - cy_j)^2}$$
computed with nested loops over a pre-allocated dist array, then scaled by unit_rate = 10.0.
Section 2 — ILP Model
pulp.LpProblem creates a minimization problem. Binary variables x[i] represent whether site $i$ is opened. Continuous variables y[i][j] bounded in $[0, 1]$ represent the fraction of client $j$’s demand assigned to server $i$.
The objective sums two components — fixed installation costs $\sum_i f_i x_i$ and weighted service costs $\sum_i \sum_j c_{ij} d_j y_{ij}$.
Three constraint groups are added:
- Demand coverage: each client’s allocation fractions must sum to exactly 1.
- Linking constraint: $y_{ij} \leq x_i$ prevents routing to closed servers.
- Capacity constraint: total demand at site $i$ cannot exceed $s_i x_i$.
CBC solver runs with msg=0 for silent output.
Section 3 — Result Extraction
pulp.value() retrieves each solved variable. open_sites collects sites where $x_i > 0.5$. Primary assignment assign[j] is found with np.argmax(y_val, axis=0). Installation and service costs are computed separately for the breakdown visualization.
Section 4 — Visualizations
Six subplots arranged in a 2 × 3 dark-themed grid:
Plot 1 — 2D Assignment Map: Geographic layout of the solution. Open servers are marked with stars ($\bigstar$), closed candidates with grey crosses. Colored lines connect each client to its primary server, giving immediate spatial intuition about the coverage structure.
Plot 2 — Load vs Capacity Bar Chart: For each open site, a capacity bar (dark) and a load bar (colored) are drawn side by side. Utilization percentages are annotated above each load bar, revealing which servers are near saturation and which have slack.
Plot 3 — Cost Breakdown Pie: Each slice corresponds to one opened server’s installation cost, plus a single slice for total service cost. The ratio of fixed to variable cost is immediately readable — a key insight for infrastructure budget planning.
Plot 4 — 3D Assignment Arcs: Clients are elevated to height $z = c_{ij^*}$ (their service cost to the primary server) while open servers sit on the ground plane $z = 0$. Arcs drop from each client down to its server. High-hanging clients are expensive to serve; the 3D view makes this cost geography visceral.
Plot 5 — 3D Service Cost Bars: Custom 3D bar volumes built with Poly3DCollection face lists are positioned at each open server’s map coordinates. Bar height equals that server’s total service cost burden. This exposes load imbalance across servers in three dimensions.
Plot 6 — 3D Minimum-Cost Surface: A $60 \times 60$ grid is swept across the map. At each point the minimum distance-based service cost to any open server is computed and rendered as a surface using the plasma colormap. Valleys in the surface correspond directly to deployed server locations. Any elevated plateau indicates a region being served from a distant site — a natural signal for where future server expansion would have the most impact.
Execution Results
================================================== Status : Optimal Total Cost : ¥100,300.6 Installation : ¥28,000.0 Service : ¥72,300.6 Servers opened : 6 → sites [0, 1, 3, 4, 6, 7] ================================================== Site 0: load=80.0/150 clients=[0, 1, 2] Site 1: load=101.0/130 clients=[3, 6, 7] Site 3: load=102.0/120 clients=[4, 5, 10] Site 4: load=67.0/160 clients=[11, 12] Site 6: load=53.0/140 clients=[13, 14] Site 7: load=60.0/110 clients=[8, 9]
Figure saved.
Key Takeaways
The ILP guarantees a globally optimal server placement under hard capacity constraints. Three structural insights emerge from this formulation. First, the linking constraint $y_{ij} \leq x_i$ is what makes this problem combinatorially hard — it couples the binary site-open decisions to the continuous allocation variables, creating a mixed-integer structure that cannot be solved by linear relaxation alone. Second, the cost trade-off is non-trivial: opening an additional server reduces service cost (shorter distances) but incurs a fixed penalty; the ILP finds the exact break-even point. Third, the 3D minimum-cost surface (Plot 6) serves as a powerful post-optimization diagnostic — the Voronoi-like valleys carved by the deployed servers reveal the effective service territories and make coverage gaps immediately visible.
