Weighted Least-Squares Facility Location

Why Weight Customer Locations?

A facility may need to serve customers who are not equally important to the decision. A hospital might give greater weight to locations with more residents; a distribution center might use demand forecasts as weights. If the objective penalizes the squared distance to each customer location, the optimal facility location is a weighted average of those locations.

The formula is simple, but its meaning depends on the objective and its assumptions. In particular, it applies to an unconstrained facility location problem with positive weights and squared Euclidean distances. We will derive the formula, prove that it gives the unique global minimum, and check it in several examples.

Model and Definition

Suppose there are \(n\) customer locations in \(d\)-dimensional Euclidean space. Write the location of customer \(i\) as the vector \(\mathbf{p}_i\in\mathbb{R}^d\), and let \(w_i>0\) be that customer's weight. The facility location is a vector \(\mathbf{x}\in\mathbb{R}^d\). The squared Euclidean distance from the facility to customer \(i\) is \(\|\mathbf{x}-\mathbf{p}_i\|^2\).

A larger weight makes a customer's squared distance contribute more to the objective. Multiplying every weight by the same positive constant changes the value of \(J\), but not the minimizing location. If the weights are relative importance scores, they need not add to one.

For planar locations, write \(\mathbf{p}_i=(a_i,b_i)\) and \(\mathbf{x}=(x,y)\). Then the objective is \(\sum_{i=1}^{n}w_i\big((x-a_i)^2+(y-b_i)^2\big)\). The weighted centroid is formed by taking a weighted average of each coordinate separately.

Why the Weighted Centroid Minimizes the Objective

Let \(W=\sum_{i=1}^{n}w_i\), so \(W>0\), and define \(\mathbf{c}=(\sum_{i=1}^{n}w_i\mathbf{p}_i)/W\). The key fact is that the weighted deviations from \(\mathbf{c}\) sum to zero:

For any proposed facility location \(\mathbf{x}\), write \(\mathbf{x}-\mathbf{p}_i=(\mathbf{x}-\mathbf{c})+(\mathbf{c}-\mathbf{p}_i)\) and expand the squared norm using the dot product. Summing the result separates the objective into a term depending on \(\mathbf{x}\) and a term independent of it.

The middle term vanishes because \(\sum_i w_i(\mathbf{c}-\mathbf{p}_i)=\mathbf{0}\). Since \(W>0\), the term \(W\|\mathbf{x}-\mathbf{c}\|^2\) is nonnegative, and it is zero exactly when \(\mathbf{x}=\mathbf{c}\). Thus \(J(\mathbf{x})\geq J(\mathbf{c})\) for every \(\mathbf{x}\), with equality only at \(\mathbf{c}\). This proves that the weighted centroid is the unique global minimum, not merely a candidate found by solving a stationarity equation.

The same result can be seen by differentiating. In coordinates, differentiating with respect to each coordinate gives \(\nabla J(\mathbf{x})=2\sum_i w_i(\mathbf{x}-\mathbf{p}_i)=2(W\mathbf{x}-\sum_i w_i\mathbf{p}_i)\). Setting the gradient equal to zero gives \(\mathbf{x}=\mathbf{c}\). The sum-of-squares identity above supplies the additional global and uniqueness check.

Worked Example: Three Customers in a Plane

Worked Example: Checking the Identity at Another Location

Worked Example: A Facility Along a Straight Road

Common Pitfall: Using the Ordinary Average

The ordinary average treats every customer as equally important. That is appropriate only when the weights are all equal. In the first example, the unweighted average of the three locations is \(((0+6+0)/3,(0+0+4)/3)=(2,4/3)\), not the weighted centroid \((2,2)\).

The ordinary average does not minimize the stated weighted objective. At \((2,4/3)\), the weighted coordinate sums are still \((12,12)\), but \(W(2,4/3)=(12,8)\). Consequently, \(\nabla J(2,4/3)=2((12,8)-(12,12))=(0,-8)\), which is not zero. The error is using an unweighted average even though the objective assigns different weights. The weighted sum in each coordinate must be divided by the total weight, not by the number of customers.

When the Formula Applies

The weighted centroid result relies on the objective being a sum of weighted squared Euclidean distances and the facility being unrestricted in \(\mathbb{R}^d\). If the facility must lie in a prescribed region, the weighted centroid might not be feasible; the unconstrained formula alone then does not solve the constrained problem. Likewise, replacing squared distance by ordinary distance changes the objective, so the derivation here no longer establishes the minimizing location.

For positive weights, the total weight is positive and the minimum is unique. More generally, the same identity and uniqueness conclusion hold for nonnegative weights provided at least one weight is positive. Negative weights do not represent positive importance in this model and do not satisfy the conditions used to prove the result.

The practical value of the formula is that it turns a multivariable minimization into a direct calculation: multiply each location by its weight, add those weighted locations, and divide by the total weight. The sum-of-squares identity then gives an exact check of both the minimum and the cost of moving the facility away from it.