betaFeedback

WorksMathematics

Projector-Based Conic Formulations and Exact Decompositions for Continuous Multifacility Location

Abstract

We study the continuous multisource facility location problem, where facility locations and the assignment of demand points must be determined simultaneously. We show that the assignment structure can be represented by orthogonal projection matrices. This observation leads to new mixed-projection conic formulations that avoid the big-M envelopes used in standard mixed-integer models. Based on these formulations, we develop exact decomposition algorithms that separate the discrete selection of the assignment projectors from location convex conic subproblems. We also derive semidefinite relaxation bounds and primal procedures that provide warm starts for the exact methods. The proposed approach draws new connections between continuous multifacility location, orthogonal projectors, and low-rank semidefinite optimization, and applies to general conic-representable distances.

Introduction

Facility location is a significant area of operations research. Decisions on the placement of plants, warehouses, service centers, emergency units, and communication infrastructure have a direct and lasting effect on operating costs and quality of service. These problems combine geometric, algebraic, combinatorial, and economic aspects. They have led to a large family of models and algorithms. General presentations of the area can be found in [2002], [2015]. Facility location is also closely related to clustering. Given several facilities, assigning each demand point to a closest facility induces a partition of the demand set. Conversely, the representatives of a distance-based clustering can be interpreted as facility locations. Thus, the distance-based pp-clustering problem considered in this paper is both a continuous multifacility location problem and a clustering problem.

Facility location problems can first be distinguished by the set of possible locations. In discrete and network location, facilities must be selected from a prescribed finite set or from a network, respectively. The seminal graph-median results of Hakimi set the basis of this line of research and introduced the pp-median structure for communication networks [1964, 1965]. In continuous location, facilities may be placed anywhere in a region of a metric space. The classical single-facility minisum model goes back to Fermat–Weber’s theory of industrial location [1909]. In its modern form, the problem seeks a point that minimizes a weighted sum of distances to the demand points. Continuous models avoid the need to specify an artificial candidate set. However, the simultaneous determination of several facility locations and the allocation of demand points makes multisource problems nonconvex and computationally challenging.

The joint location and allocation decision is the main difficulty in these problems. This hardship has guided much of the research on continuous location. For a single facility, optimality conditions and iterative methods use convexity and the geometry of sums of distances Beck et al. [ [1], Fekete et al. [ [26]. When several facilities are considered, the unknown allocation lends a combinatorial dimension. Cooper [ [19] made this structure explicit. Kuenne and Soland [ [31] later proposed exact and approximate procedures for the multisource Weber problem. This line led to exact enumeration and set-covering methods Rosing [ [41], difference-of-convex global optimization Chen et al. [ [17], and geometric branch-and-bound schemes such as the big-triangle–small-triangle method Blanquero and Carrizosa [ [12], Drezner and Suzuki [ [24].

This difficulty also explains the growing interest in the development of heuristic methods. Cooper’s alternating location–allocation algorithm repeatedly assigns each demand point to a closest facility and then solves an independent single-facility problem for every cluster Cooper [ [20]. Projection, neighborhood-search, decomposition, and multistart methods extend this basic idea and allow larger instances to be tackled (see, e.g. Brimberg et al. [ [14]). Exact and heuristic methods play different but related roles. Fast heuristics provide warm feasible solutions and starting configurations. Exact methods provide the global bounds required to certify the quality of these solutions. Recent work also studies how to construct suitable starting configurations Drezner and Brimberg [ [22].

Continuous location has evolved well beyond the classical planar Euclidean setting. Current models accommodate general ℓτ\ell_{\tau} distances, heterogeneous metrics, and ordered multifacility criteria Blanco et al. [ [6, 8, 7, 9]. This breadth requires solution methods that are not tied to a particular distance, dimension, or objective. Much of the exact and heuristic literature exploits geometric structure through Voronoi assignments, separability under a fixed allocation, and planar subdivision bounds Blanquero and Carrizosa [ [12], Drezner and Suzuki [ [24], Rodríguez-Chía et al. [ [40]. Although effective in the planar Euclidean setting, their bounds and convergence arguments often rely on specific bisectors, subdivisions, or distance properties, which hinders their extension to higher dimensions and general conic-representable distances. Moreover, geometry does not remove the underlying combinatorial difficulty Megiddo and Supowit [ [37].

Mathematical optimization gives another way to represent this structure. Standard compact models use binary variables to represent the allocation and big-MM envelopes to couple those variables with distances. They can accommodate broad classes of conic-representable distances, but their convex relaxation bounds may be weak and choosing valid big-MM constants can be difficult. Perspective reformulations can strengthen mixed-integer nonlinear models with indicator variables Günlük and Linderoth [ [28], although they still retain an explicit binary description of the underlying decisions. Semidefinite optimization provides a different approach. Results in combinatorial optimization showed that matrix liftings can be used to obtain convex relaxations of quadratic structures Goemans [ [27], Vandenberghe and Boyd [ [43]. Moment and semidefinite hierarchies extended this idea to polynomial optimization Lasserre [ [33]. Semidefinite relaxations of quadratic problems and low-rank factorization methods also made this approach useful for many nonconvex models Burer and Monteiro [ [15, 16], Lemon et al. [ [34], Luo et al. [ [36]. The connection is especially direct for clustering. Peng and Xia introduced a projection-matrix framework for kk-means-type clustering, and Peng and Wei subsequently developed its semidefinite approximation Peng and Wei [2007], Peng and Xia [ [39]. Later work established recovery guarantees and exactness properties for related conic formulations Li et al. [ [35].

Rank remains the main nonconvex element. Convex surrogates do not in general enforce the exact rank of a discrete partition, while low-rank factorizations reduce dimension but remain nonconvex Burer and Monteiro [ [15, 16]. Exact approaches instead combine convex relaxations with branching or cutting planes. Advances in conic outer approximation have made this combination increasingly practical Bertsimas and Cory-Wright [ [2], Coey et al. [ [18].

Mixed-projection conic optimization (MPCO), introduced in Bertsimas et al. [ [3], combines several of these ideas. It represents rank through an orthogonal projector satisfying P2=PP^{2}=P. This condition is the matrix version of the binary identity z2=zz^{2}=z. Regularization and conic duality then separate the choice of a projector from a convex conic subproblem. This separation gives globally valid cuts, semidefinite relaxation bounds, and primal recovery in the same approach.

The purpose of this paper is to study multisource continuous location through the lens of orthogonal projectors. An allocation matrix naturally defines an orthogonal projector. As a result, the partition structure can be represented directly instead of being hidden in binary assignment-distance products. We show that this observation yields big-MM-free conic formulations for general conic-representable distances and leads to exact decomposition algorithms. The projector-based formulations give a new description of the relation between location, allocation, and rank. It also provides a baseline for formulations and algorithms that do not depend on planar Euclidean geometry.

The paper has three main contributions. First, we derive mixed-projection conic formulations of distance-based pp-clustering that replace the assignment-distance products and their associated big-MM constraints. Second, we develop globally valid decomposition methods for these formulations. The main algorithmic contribution is an exact outer-approximation method for the disaggregated low-rank model. A global projector master coordinates conic subproblems whose values generate valid cuts. We also derive an exact logic-based decomposition for the pairwise projector-based model. Third, we propose alternating and semidefinite-rounding procedures that generate high-quality feasible solutions. These procedures are used as warm starts for the exact methods.

The remainder of the paper is organized as follows. § 3 derives the pairwise projection formulation and its exact logic-based decomposition. § 4 develops the low-rank and mixed-projection formulations together with an exact outer-approximation algorithm. § 5 collects the strengthening and heuristic procedures and explains how they strengthen and initialize the exact solution process. § 6 reports the numerical experiments and § 7 concludes.

Multifacility Location and Orthogonal Projectors

Lowercase characters denote scalars, bold lowercase characters denote vectors, and uppercase characters denote matrices. For n∈Nn \in\mathbb{N}, we write [n]:={1,…,n}[n] := \{1,\ldots,n\}. The vectors of all ones in Rn\mathbb{R}^{n} and the identity matrix in Rn×n\mathbb{R}^{n \times n} are denoted by ene_n and InI_n, respectively. Notation ϵi\epsilon_i stands for the iith vector of the canonical basis.

The demand points and facility locations belong to Rm\mathbb{R}^{m}, which is endowed with a metric dd. We assume that this metric is conic representable. This means that, for every fixed a∈Rma \in\mathbb{R}^{m}, the epigraph of d(a,⋅)d(a,\cdot) is the projection of a conic system. Formally, there exist an integer q≥0q \ge0, a proper cone K\mathcal{K}, and an affine map L\mathcal{L} of suitable dimension such that

d(a,x)≤w  ⟺  ∃u∈Rq:L(x,w,u)∈K.d(a,x) \le w \iff\exists u \in\mathbb{R}^{q}: \mathcal{L}(x,w,u) \in\mathcal{K}.

Here, a proper cone is closed, convex, solid, and pointed. The cone, the affine map, and the auxiliary dimension may depend on the distance under consideration. Every norm-based distance is conic representable.

The class also includes several distances beyond the usual Euclidean and ℓp\ell_p cases. For example, an anisotropic or Mahalanobis distance can be written as

d(a,x)=(x−a)TQ(x−a)=∥L(x−a)∥2,Q=LTL≻0,d(a,x)=\sqrt{(x-a)^{T}Q(x-a)}=\lVert L(x-a)\rVert_{2}, \qquad Q=L^{T}L \succ0,

and therefore has a second-order cone representation Ward and Wendell [ [44], Zhou et al. [ [46]. Polyhedral distances of the form

d(a,x)=max⁡1≤h≤H{chT(x−a)}d(a,x)=\max_{1\le h\le H}\{c_h^{T}(x-a)\}

where the vectors chc_h define a symmetric and point-separating polytope, are linearly representable by imposing chT(x−a)≤wc_h^{T}(x-a)\le w for every h∈[H]h\in[H] Ward and Wendell [ [44]. Distances under refraction, where travel crosses regions with different transportation costs, are also conic representable when each regional distance is conic representable. In this case, the crossing points are auxiliary variables and the total distance is the minimum sum of the regional distances Blanco et al. [ [8]. Another example is the finite-support Wasserstein distance between two discrete distributions. For a fixed ground-cost matrix CC, it is the optimal value of the transportation problem

min⁡Π≥0{⟨C,Π⟩:Πe=a, ΠTe=x},\min_{\Pi\ge0}\{\langle C,\Pi\rangle:\Pi e=a,\ \Pi^{T}e=x\},

so its epigraph has a linear extended formulation Cuturi and Doucet [ [21]. These examples show that conic representability may follow from a lifting even when the metric is not given directly by a standard norm.

For X∈Rm×nX\in\mathbb{R}^{m\times n}, its jjth column is denoted by xj∈Rmx_j\in\mathbb{R}^{m}, and its (i,j)(i,j) entry is denoted by xijx_{ij}. The superscript TT denotes transposition, and Tr⁡(X)\operatorname{Tr}(X) denotes the trace of a square matrix XX. Given matrices Xi∈Rmi×niX_i\in\mathbb{R}^{m_i\times n_i} for i∈[n]i\in[n], the matrix Blockdiag⁡(Xi)i∈[n]\operatorname{Blockdiag}(X_i)_{i\in[n]} has the matrices XiX_i as its diagonal blocks and zeros elsewhere. Its dimension is (∑i=1nmi)×(∑i=1nni)(\sum_{i=1}^{n}m_i)\times(\sum_{i=1}^{n}n_i). The Euclidean and Frobenius inner products are, respectively,

⟨x,y⟩:=xTyand⟨X,Y⟩:=Tr⁡(XTY).\langle x,y\rangle:=x^{T}y \qquad\text{and}\qquad\langle X,Y\rangle:=\operatorname{Tr}(X^{T}Y).

We consider a continuous multisource facility location problem with demand points set {a1,…,an}⊂Rm\{a_1,\ldots,a_n\}\subset\mathbb{R}^{m}, nonnegative weights ωi\omega_i, and pp facilities with locations x1,…,xp∈Rmx_1,\ldots,x_p\in\mathbb{R}^{m}. Each demand point is served by a closest facility. Since the formulation below requires every facility to serve at least one demand point, we assume throughout that 2≤p≤n2\le p\le n. The problem is

min⁡X∈Rm×p∑i=1nωimin⁡1≤j≤pd(ai,xj),\min_{X\in\mathbb{R}^{m\times p}}\sum_{i=1}^{n}\omega_i\min_{1\le j\le p}d(a_i,x_j),

The binary variable zijz_{ij} takes value one when demand point ii is assigned to facility jj. This gives the mixed-integer nonlinear formulation:

min⁡∑i=1n∑j=1pωizijd(ai,xj)\min\sum_{i=1}^{n}\sum_{j=1}^{p}\omega_i z_{ij}d(a_i,x_j)
∑j=1pzij=1,∀i∈[n];(1)\sum_{j=1}^{p}z_{ij}=1,\qquad\forall i\in[n]; \tag*{(1)}
∑i=1nzij≥1,∀j∈[p];(2)\sum_{i=1}^{n}z_{ij}\ge1,\qquad\forall j\in[p]; \tag*{(2)}
xj∈Rm,∀j∈[p];x_j\in\mathbb{R}^{m},\qquad\forall j\in[p];
zij∈{0,1},∀i∈[n], j∈[p].z_{ij}\in\{0,1\},\qquad\forall i\in[n],\,j\in[p].

When dd is induced by an ℓp\ell_p-norm, the products zijd(ai,xj)z_{ij}d(a_i,x_j) in the objective are usually convexified by combining pp-order cone constraints with big-MM envelopes Blanco et al. [ [9, 7]. For rational values of the norm parameter pp, these pp-order cones admit extended representations using second-order cones Blanco et al. [ [10], Blanco and Martínez-Antón [ [5]. Thus, the resulting models can be written as mixed-integer second-order cone programs and solved with available conic optimization solvers. In this formulation, one introduces an auxiliary continuous variable for each distance and then uses the McCormick envelope for the product of this variable and the binary variable zijz_{ij}. In an epigraph formulation, this gives constraints of the form

tij≥d(ai,xj)−Mi(1−zij),tij≥0,t_{ij}\ge d(a_i,x_j)-M_i(1-z_{ij}),\qquad t_{ij}\ge0,

and the objective becomes ∑i=1n∑j=1pωitij\sum_{i=1}^{n}\sum_{j=1}^{p}\omega_i t_{ij}. The constants can be selected separately for each demand point as

Mi:=max⁡1≤k≤nd(ai,ak).M_i:=\max_{1\le k\le n}d(a_i,a_k).

Indeed, for norm-based distances, a facility serving a nonempty set of demand points can be located in their convex hull without increasing its service cost. Hence, facility location at optimality belongs to the convex hull of the demand points. By convexity of d(ai,⋅)d(a_i,\cdot), its maximum over this convex hull is attained at a demand point, which proves that MiM_i is a valid upper bound.

Constraint (1) assigns every demand point to exactly one facility, and constraint (2) ensures that every facility serves a nonempty set of demand points.

We next introduce the notation used to reformulate these assignment decisions. We let Sn\mathcal{S}^{n} denote the vector space of real n×nn\times n symmetric matrices (PT=PP^{\mathsf{T}}=P). A matrix P∈Rn×nP\in\mathbb{R}^{n\times n} is a projection matrix if P2=PP^2=P. If, in addition, P∈SnP\in\mathcal{S}^{n}, then PP is an orthogonal projection matrix. The eigenvalues of an orthogonal projector satisfy λi2=λi\lambda_i^2=\lambda_i and therefore belong to {0,1}\{0,1\}. Consequently, Rank⁡(P)=Tr⁡(P)\operatorname{Rank}(P)=\operatorname{Tr}(P). We use

Pn:={P∈Sn:P2=P}\mathcal{P}^{n}:=\{P\in\mathcal{S}^{n}:P^2=P\}

for the set of n×nn\times n orthogonal projection matrices, and

Pkn:={P∈Sn:P2=P, Tr⁡(P)=k}\mathcal{P}^{n}_{k}:=\{P\in\mathcal{S}^{n}:P^2=P,\ \operatorname{Tr}(P)=k\}

for the subset of projectors with rank kk.

Orthogonal projectors provide a matrix representation of linear subspaces. If PP has rank rr, then it can be written as

P=UUT,UTU=IrP = UU^{T}, \qquad U^{T}U = I_r

where the columns of U∈Rn×rU \in\mathbb{R}^{n \times r} form an orthonormal basis of the range of PP. In particular, every rank-one orthogonal projector has the form P=uuTP = uu^{T} for some u∈Rnu \in\mathbb{R}^{n} with uTu=1u^{T}u = 1. Low-rank factorizations of this type are widely used to replace a large positive semidefinite matrix variable by a smaller, but nonconvex, factorized model Burer and Monteiro [ [15, 16], Lemon et al. [ [34].

The constraints P2=PP^2 = P and Rank⁡(P)=k\operatorname{Rank}(P) = k are nonconvex. A standard semidefinite relaxation replaces idempotency by the spectral constraints 0⪯P⪯In0 \preceq P \preceq I_n together with Tr⁡(P)=k\operatorname{Tr}(P) = k. It is well-known that these constraints describe the convex hull of orthogonal projectors with rank kk. Such semidefinite relaxations have been used to represent partitions in kk-means-type models Peng and Wei [ [38], Peng and Xia [ [39]. In contrast, mixed-projection conic optimization keeps the projector constraint explicit and treats it as the matrix counterpart of a binary requirement Bertsimas et al. [ [3]. General methods for rank-constrained and low-rank semidefinite optimization are discussed in Lemon et al. [ [34], Sun and Dai [ [42].

Let Z=(zij)i,j∈{0,1}n×pZ = (z_{ij})_{i,j} \in\{0,1\}^{n \times p} be the assignment matrix, and let zjz_j denote its jjth column. Since the rows of ZZ contain exactly one nonzero entry, different columns have disjoint supports. Thus,

ZTZ=diag⁡(zjTzj)j∈[p]=diag⁡(enTzj)j∈[p].Z^{T}Z = \operatorname{diag}\left(z_j^{T}z_j\right)_{j\in[p]} = \operatorname{diag}\left(e_n^{T}z_j\right)_{j\in[p]}.

All diagonal entries are positive by (2), so ZTZZ^{T}Z is invertible. We can therefore define

P:=Z(ZTZ)−1ZT∈Pn∩R+n×n.P := Z(Z^{T}Z)^{-1}Z^{T} \in\mathcal{P}^{n} \cap\mathbb{R}_{+}^{n\times n}.

which is the orthogonal projector onto the column space of ZZ. This matrix is entrywise nonnegative. Constraint (1) can be written as Zep=enZe_p = e_n. Hence, ene_n belongs to the column space of ZZ, so that Pen=enPe_n = e_n. Since all pp columns of ZZ are nonzero and mutually orthogonal, Rank⁡(Z)=p\operatorname{Rank}(Z) = p. Therefore, Tr⁡(P)=Rank⁡(P)=p\operatorname{Tr}(P) = \operatorname{Rank}(P) = p.

The projector PP can also be disaggregated by facility as

P=∑j=1pPj,Pj:=zjzjTenTzj.P = \sum_{j=1}^{p} P_j, \qquad P_j := \frac{z_j z_j^{T}}{e_n^{T}z_j}.

For every j∈[p]j \in[p], Pj∈P1n∩R+n×nP_j \in\mathcal{P}_{1}^{n} \cap\mathbb{R}_{+}^{n\times n} is the rank-one orthogonal projector associated with the demand points assigned to facility jj. In particular, Pjen=zjP_j e_n = z_j. These identities will be used in the projector-based formulations developed in the subsequent sections.

Pairwise Formulation

We first derive a projector-based conic formulation directly from the assignment model (MICO). The main idea is to replace the indicator vector of each facility by the rank-one projector onto the subspace that it spans. To recover the contribution of a cluster from this normalized projector, we write its service cost as an average of pairwise quantities. This produces an exact formulation in which the assignment decisions are carried only by nonnegative orthogonal projectors. Unlike a standard mixed-integer conic formulation, the resulting model does not require big-MM constants.

For every x∈Rmx \in\mathbb{R}^{m}, define the symmetric matrix Y(x)=(yik(x))i,k∈[n]∈SnY(x) = (y_{ik}(x))_{i,k\in[n]} \in\mathcal{S}^{n} componentwise by

yik(x):=ωid(ai,x)+ωkd(ak,x).y_{ik}(x) := \omega_i d(a_i,x) + \omega_k d(a_k,x).

The entry yik(x)y_{ik}(x) is the total weighted cost of serving demand points ii and kk from a same facility located at xx. Hence, Y(xj)Y(x_j) collects all pairwise service costs associated with facility jj. We obtain

∑i=1nωizijd(ai,xj)=12enTzj∑i=1n∑k=1nzijzkjyik(xj)=12⟨Pj,Y(xj)⟩.(3)\sum_{i=1}^{n}\omega_i z_{ij}d(a_i,x_j)=\frac{1}{2e_n^{T}z_j}\sum_{i=1}^{n}\sum_{k=1}^{n}z_{ij}z_{kj}y_{ik}(x_j) =\frac{1}{2}\langle P_j,Y(x_j)\rangle. \tag*{(3)}

The factor 1/21/2 corrects the two occurrences of every individual service cost in yik(xj)y_{ik}(x_j). Identity (3) is the link between the classical assignment objective and the projector-based model.

Theorem 1. The multisource facility location problem has the following exact formulation:

min⁡12∑j=1p⟨Pj,Y(xj)⟩(PW)s.t.∑j=1pPjen=en,Pj∈P1n∩R+n×n,xj∈Rm,∀j∈[p].\begin{aligned} \min\quad& \frac{1}{2}\sum_{j=1}^{p}\langle P_j,Y(x_j)\rangle&& \text{(PW)}\\ \text{s.t.}\quad& \sum_{j=1}^{p}P_je_n=e_n,\\ & P_j\in\mathcal{P}_1^n\cap\mathbb{R}_{+}^{n\times n},\quad x_j\in\mathbb{R}^{m},\quad\forall j\in[p]. \end{aligned}

The assignment vectors of any feasible solution of (PW) are recovered as zj=Pjenz_j=P_je_n, j∈[p]j\in[p]. Conversely, every feasible assignment matrix ZZ induces feasible projectors through

Pj=zjzjTenTzj,j∈[p].(4)P_j=\frac{z_jz_j^{T}}{e_n^{T}z_j},\qquad j\in[p]. \tag*{(4)}

Both transformations preserve the objective value.

Proof. Let ZZ be a feasible assignment matrix. Constraint (2) implies enTzj>0e_n^{T}z_j>0 for every j∈[p]j\in[p], so the matrices in (4) are well defined. Each PjP_j is entrywise nonnegative, symmetric, idempotent, and has rank one. Also, Pjen=zjP_je_n=z_j. It follows from (1) that ∑j=1pPjen=en\sum_{j=1}^{p}P_je_n=e_n, and (3) proves that the objective value is preserved.

For the reverse implication, consider a feasible collection (Pj)j∈[p](P_j)_{j\in[p]} in (PW) and set zj=Pjenz_j=P_je_n. Nonnegativity and the coupling constraint give 0≤zij≤10\le z_{ij}\le1 and ∑j=1pzij=1\sum_{j=1}^{p}z_{ij}=1 for every i∈[n]i\in[n]. Idempotency and symmetry yield

zjTzj=enTPjTPjen=enTPjen=enTzj.z_j^{T}z_j=e_n^{T}P_j^{T}P_je_n=e_n^{T}P_j e_n=e_n^{T}z_j.

Consequently,

0=∑j=1p(enTzj−zjTzj)=∑i=1n∑j=1pzij(1−zij).0=\sum_{j=1}^{p}(e_n^{T}z_j-z_j^{T}z_j)=\sum_{i=1}^{n}\sum_{j=1}^{p}z_{ij}(1-z_{ij}).

Every term in the last sum is nonnegative. Therefore, zij∈{0,1}z_{ij}\in\{0,1\} for all i∈[n]i\in[n] and j∈[p]j\in[p]. The linear equality excludes the zero projector, so each induced cluster is nonempty. Finally, a nonnegative rank-one projector whose row-sum vector is zjz_j must satisfy Pj=zjzjT/(enTzj)P_j=z_jz_j^{T}/(e_n^{T}z_j). Applying (3) completes the proof. □

We next express (PW) in the value-function form used in mixed-projection conic optimization. Define the epigraph set

E:={(W,x)∈Sn×Rm:wik≥yik(x), i,k∈[n]}.(5)\mathcal{E}:=\{(W,x)\in\mathbb{S}^{n}\times\mathbb{R}^{m}:w_{ik}\ge y_{ik}(x),\ i,k\in[n]\}. \tag*{(5)}

and let δE\delta_{\mathcal{E}} be its extended-valued indicator function. Thus, δE(W,x)=0\delta_{\mathcal{E}}(W,x)=0 when (W,x)∈E(W,x)\in\mathcal{E} and +∞+\infty otherwise. Since the metric dd is conic representable, set (5) is also conic representable because each of its inequalities is an epigraph constraint for a nonnegative weighted sum of two distances.

For P∈P1n∩R+n×nP\in\mathcal{P}^{n}_{1}\cap\mathbb{R}^{n\times n}_{+}, consider the extended-valued function

f(P):=inf⁡V,W,x{Tr⁡(V)+δE(W,x):V=PW}.(6)f(P):=\inf_{V,W,x}\{\operatorname{Tr}(V)+\delta_{\mathcal{E}}(W,x):V=PW\}. \tag*{(6)}

The matrix VV isolates the nonconvexity stemming from the product between the projector and the epigraph variable. For fixed PP, the equality V=PWV=PW is linear, so (6) is a conic optimization problem.

Theorem 2. For every P∈P1n∩R+n×nP\in\mathcal{P}^{n}_{1}\cap\mathbb{R}^{n\times n}_{+},

f(P)=inf⁡x∈Rm⟨P,Y(x)⟩.(7)f(P)=\inf_{x\in\mathbb{R}^{m}}\langle P,Y(x)\rangle. \tag*{(7)}

Consequently, (PW)(\mathrm{PW}) is equivalent to

min⁡12∑j=1pf(Pj)\min\quad\frac{1}{2}\sum_{j=1}^{p}f(P_j)
s.t.∑j=1pPjen=en,\text{s.t.}\quad\sum_{j=1}^{p}P_j e_n=e_n,
Pj∈P1n∩R+n×n,∀j∈[p].P_j\in\mathcal{P}^{n}_{1}\cap\mathbb{R}^{n\times n}_{+},\quad\forall j\in[p].
(PW-VF)\mathrm{(PW\text{-}VF)}

In particular, (PW-VF)(\mathrm{PW\text{-}VF}) separates the discrete partition structure, represented by the projectors, from the location conic subproblems represented by ff.

Proof. Fix P∈P1n∩R+n×nP\in\mathcal{P}^{n}_{1}\cap\mathbb{R}^{n\times n}_{+}. Eliminating VV from (6) gives

f(P)=inf⁡(W,x)∈ETr⁡(PW)=inf⁡(W,x)∈E⟨P,W⟩,f(P)=\inf_{(W,x)\in\mathcal{E}}\operatorname{Tr}(PW)=\inf_{(W,x)\in\mathcal{E}}\langle P,W\rangle,

where the latter equality follows because PP and WW are symmetric. For any (W,x)∈E(W,x)\in\mathcal{E}, the matrix W−Y(x)W-Y(x) is entrywise nonnegative. Since PP is also entrywise nonnegative,

⟨P,W⟩≥⟨P,Y(x)⟩.\langle P,W\rangle\ge\langle P,Y(x)\rangle.

Equality is attained by choosing W=Y(x)W=Y(x). Taking the infimum over xx proves (7). Substitution of this identity in (PW)(\mathrm{PW}) proves the equivalence. □\square

The value-function representation does not by itself convexify the idempotency requirement. It does, however, separate the selection of a partition from the continuous location decisions. This separation leads directly to the following exact decomposition method and completes our analysis of the pairwise projector-based model.

Exact Logic-Based Decomposition

Let

Pn,p:={(P1,…,Pp):Pj∈P1n∩R+n×n, j∈[p], ∑j=1pPjen=en}.(8)\mathcal{P}^{n,p}:=\left\{(P_1,\ldots,P_p):P_j\in\mathcal{P}^{n}_{1}\cap\mathbb{R}^{n\times n}_{+},\ j\in[p],\ \sum_{j=1}^{p}P_j e_n=e_n\right\}. \tag*{(8)}

By Theorem 1, Pn,p\mathcal{P}^{n,p} is precisely the set of labeled nonempty partitions represented through orthogonal projectors. For a fixed projector collection P=(P1,…,Pp)∈Pn,p\mathbf{P}=(P_1,\ldots,P_p)\in\mathcal{P}^{n,p}, define the location subproblem value

g(P):=min⁡X∈Rm×p12∑j=1p⟨Pj,Y(xj)⟩=12∑j=1pf(Pj).(9)g(\mathbf{P}) := \min_{X\in\mathbb{R}^{m\times p}} \frac{1}{2}\sum_{j=1}^{p}\langle P_j,Y(x_j)\rangle= \frac{1}{2}\sum_{j=1}^{p} f(P_j). \tag*{(9)}

The equality follows from (7). Thus, g(P)g(\mathbf{P}) is obtained by solving pp independent conic programs.

To construct a master problem, consider an evaluated projector collection P‾=(P‾1,…,P‾p)\overline{\mathbf{P}}=(\overline{P}_1,\ldots,\overline{P}_p), set z‾j=P‾jen\overline{z}_j=\overline{P}_j e_n, and define

ΔP‾(P):=∑j=1pz‾jT(en−Pjen).(10)\Delta_{\overline{\mathbf{P}}}(\mathbf{P}) := \sum_{j=1}^{p}\overline{z}_j^{T}(e_n-P_j e_n). \tag*{(10)}

For P∈Pn,p\mathbf{P}\in\mathcal{P}^{n,p}, the vector PjenP_j e_n is the binary incidence vector of cluster jj. Consequently, ΔP‾(P)=0\Delta_{\overline{\mathbf{P}}}(\mathbf{P})=0 if P\mathbf{P} and P‾\overline{\mathbf{P}} represent the same labeled partition, whereas ΔP‾(P)≥1\Delta_{\overline{\mathbf{P}}}(\mathbf{P})\ge1 for every different labeled partition. Since g(P)≥0g(\mathbf{P})\ge0, the logic-based optimality cut

θ≥g(P‾)(1−ΔP‾(P))(11)\theta\ge g(\overline{\mathbf{P}})(1-\Delta_{\overline{\mathbf{P}}}(\mathbf{P})) \tag*{(11)}

is valid over Pn,p\mathcal{P}^{n,p}. It imposes the exact location cost at P‾\overline{\mathbf{P}} and becomes redundant at every other labeled partition. After evaluating the projector collections P1,…,Pr\mathbf{P}_1,\ldots,\mathbf{P}_r, the master problem is

min⁡P∈Pn,p, θ≥0θ(PW-LBr)s.t.θ≥g(Pℓ)(1−ΔPℓ(P)),∀ℓ∈[r].\begin{aligned} \min_{\mathbf{P}\in\mathcal{P}^{n,p},\,\theta\ge0}\quad&\theta&&\text{(PW-LB}_{r}\text{)}\\ \text{s.t.}\quad&\theta\ge g(\mathbf{P}_{\ell})(1-\Delta_{\mathbf{P}_{\ell}}(\mathbf{P})), &&\forall\ell\in[r]. \end{aligned}

Proposition 1. The optimal value of the master problem (PW-LB_{r}) is a lower bound on that of (PW). If a master solution not evaluated previously is selected at every iteration, then the procedure that alternates between (PW-LB_{r}) and the location subproblem (9) terminates after finitely many iterations with a globally optimal solution of (PW).

Proof. Cut (11) never overestimates the value of a partition. Indeed, its right-hand side equals g(P‾)g(\overline{\mathbf{P}}) at the evaluated partition and is nonpositive at any other partition, while all location costs are nonnegative. Therefore, the master is a relaxation of the value-function problem and supplies a valid lower bound. The set Pn,p\mathcal{P}^{n,p} represents finitely many labeled partitions. Each iteration evaluates a new member of this set and adds a cut that reproduces its exact value. Hence, after finitely many iterations, either the master lower bound equals the best evaluated value or every partition has been evaluated. In both cases, the best evaluated solution is globally optimal. □

This master can be strengthened by exploiting the facility-wise separability of g(P)g(\mathbf{P}) (9). It introduces variables θj≥0\theta_j\ge0, imposes θ≥12∑j=1pθj\theta\ge\frac{1}{2}\sum_{j=1}^{p}\theta_j, and minimizes θ\theta. Let C⊂[n]C\subset[n] represent the cluster of demand points induced by a previously evaluated rank-one projector P‾j\overline{P}_j. If L(C)L(C) denotes a dual-certified value for the single-facility problem f(P‾j)f(\overline{P}_j), it adds

θj≥L(C)(∑i∈Ce‾iTPjen−∣C∣+1),j∈[p].(12)\theta_j\ge L(C)\left(\sum_{i\in C}\overline{e}_i^{T}P_j e_n-|C|+1\right),\qquad j\in[p]. \tag*{(12)}

This inequality remains valid when facility jj contains CC, so a certified cluster value can strengthen many partitions and every facility label. The aggregate cut (11) is retained. The program can be written as a nonconvex quadratically constrained problem by factoring Pj=ujujTP_j=u_j u_j^{T}. Any global optimization solver able to handle this master can be used. At each master incumbent, the location subproblem (9) can be handled by any suitable conic solver, and cut (11) can be added through a lazy-constraint callback. Alternatively, an explicit solve–separate–resolve loop can solve the master, certify the selected partition through the conic subproblem, add the resulting cuts, and solve the strengthened master again. The best evaluated value is an upper bound, while the master value is a lower bound. The method therefore provides a global optimality certificate when these bounds coincide. The cuts are intentionally simple and can be weak. The warm-start procedures described in § 5, together with symmetry-breaking conditions for facility labels, can substantially reduce the number of partitions evaluated.

Remark 1. Notice that a similar exact decomposition scheme, developed above to tackle the mixed-projection program (PW), can be adapted to the mixed-integer program (MICO). We can express (MICO) in the value-function form. Define the epigraph set

E~:={(W,X)∈Rn×p×Rm×p:wij≥ωid(ai,xj), i∈[n],j∈[p]}.\widetilde{\mathcal E}:=\{(W,X)\in\mathbb{R}^{n\times p}\times\mathbb{R}^{m\times p}:w_{ij}\geq\omega_i d(a_i,x_j),\ i\in[n],j\in[p]\}.

For an assignment matrix Z∈{0,1}n×pZ\in\{0,1\}^{n\times p} consider the extended-valued function

f~(Z):=inf⁡W,X{Tr⁡(V)+δE~(W,X):V=ZTW}.\widetilde{f}(Z):=\inf_{W,X}\{\operatorname{Tr}(V)+\delta_{\widetilde{\mathcal E}}(W,X):V=Z^{T}W\}.

Now, the matrix VV isolates the product between binary variables and the continuous epigraph variables. For fixed ZZ, the equality V=ZTWV=Z^{T}W is linear, so f~(Z)\widetilde{f}(Z) is a conic optimization problem which serves as a tractable subproblem in the decomposition scheme. It is not difficult to see that

min⁡Z∈{0,1}n×p{f~(Z):Zep=en, ZTen≥ep}\min_{Z\in\{0,1\}^{n\times p}}\{\widetilde{f}(Z):Z e_p=e_n,\ Z^{T}e_n\geq e_p\}

is equivalent to (MICO). Hence, we can add the logic-based optimality cuts

θ≥f~(Z‾)(Tr⁡(Z‾TZ)+1−enTZ‾ep)\theta\geq\widetilde{f}(\overline{Z})\left(\operatorname{Tr}(\overline{Z}^{T}Z)+1-e_n^{T}\overline{Z}e_p\right)

provided by the subproblem evaluated at a fixed assignment Z‾\overline{Z} in order to construct the master problem as detailed above. This approach handles nonconvexity directly within the decomposition framework, without requiring the model to be convexified through big-M techniques, as is commonly done in the state-of-the-art literature. However, this remains an oracle-based reformulation of the classical assignment model. Each cut is informative only at its evaluated assignment, so all labeled assignments may still need to be examined. The master also retains npnp binaries and facility-label symmetry, and each new assignment requires a conic subproblem. In contrast, the projector formulations admit semidefinite relaxation bounds, projection inequalities, trace bounds, and matrix cuts that act on several partitions, while the sum of rank-one projectors is label invariant. Thus, eliminating big-M constants from the assignment model does not provide the same lower-bounding and symmetry-reduction mechanisms. To the best of our knowledge, this approach has not yet been explored in the context of continuous multifacility location. Although this idea is not the focus of the present paper, it represents a promising direction for future research.

The next section develops a lifted formulation that represents the projector-location interaction through conic and semidefinite constraints.

Low-Rank Formulations

The pairwise model developed in § 3 gives an exact projector-based representation of the assignment decisions. Its objective still couples each projector with a matrix of distances that depends on an unknown facility location. We now derive a second representation that moves this interaction from the objective to a projection constraint. The derivation has two steps. We first use the perspective of each distance to represent an active assignment-location term without a big-MM constant. We then relate the assignment and location variables through orthogonal projectors. The result is an exact mixed-projection conic optimization model whose continuous part is conic once the projectors are fixed.

Perspective formulations strengthen mixed-integer convex models with indicator variables Günlük and Linderoth [ [28]. Low-rank factorizations and rank-constrained semidefinite models have been studied extensively Burer and Monteiro [ [15, 16], Lemon et al. [ [34], Sun and Dai [ [42]. Our construction combines these ideas within the low-rank MPCO framework of Bertsimas et al. [ [3]. In contrast with the standard assignment formulation, it requires neither binary variables nor big-MM envelopes.

Given a feasible assignment and its centers, define

Qj:=zjxjT∈Rn×m,∀j∈[p].(13)Q_j := z_j x_j^{\mathsf T} \in\mathbb{R}^{n \times m}, \quad\forall j \in[p]. \tag*{(13)}

The active distance can be written using only PjP_j and QjQ_j. For this purpose, let di(x):=d(ai,x)d_i(x) := d(a_i, x) and denote its recession function by di∞d_i^{\infty}. We define the closed perspective of did_i as

d^i(α,q):={αdi(q/α),α>0,di∞(q),α=0,+∞,α<0.\widehat{d}_i(\alpha,q) := \begin{cases} \alpha d_i(q/\alpha), & \alpha> 0,\\ d_i^{\infty}(q), & \alpha= 0,\\ +\infty, & \alpha< 0. \end{cases}

This definition depends only on the arguments (α,q)(\alpha,q) and does not involve an assignment variable. In particular, d^i(1,x)=d(ai,x)\widehat{d}_i(1,x) = d(a_i,x) and d^i(0,0)=di∞(0)=0\widehat{d}_i(0,0) = d_i^{\infty}(0) = 0. For a feasible assignment, Pjen=zjP_j e_n = z_j and QjTϵi=zijxjQ_j^{\mathsf T}\epsilon_i = z_{ij}x_j. Therefore,

d^i(ϵiTPjen,QjTϵi)=zijd(ai,xj).(14)\widehat{d}_i\left(\epsilon_i^{\mathsf T}P_j e_n,Q_j^{\mathsf T}\epsilon_i\right) = z_{ij}d(a_i,x_j). \tag*{(14)}

In formulations (LR-D), and (LR-A), the two arguments of d^i\widehat{d}_i are the decision expressions ϵiTPjen\epsilon_i^{\mathsf T}P_j e_n and QjTϵiQ_j^{\mathsf T}\epsilon_i. Thus, neither zijz_{ij} nor xjx_j is a decision variable in these models. They are used only in (14) to prove equivalence with the original formulation. The epigraph of d^i\widehat{d}_i is obtained by homogenizing an epigraph representation of did_i, and is therefore conic representable whenever the epigraph of did_i is conic representable Günlük and Linderoth [ [28].

More specifically, suppose that a conic representation of did_i is

di(x)≤w⟺∃u: Aix+biw+Ciu+ci∈Ki,(15)d_i(x) \leq w \quad\Longleftrightarrow\quad\exists u:\ A_i x + b_i w + C_i u + c_i \in K_i, \tag*{(15)}

Homogenizing (15) gives

tij≥d^i(ϵiTPjen,QjTϵi)⟺{ϵiTPjen≥0,AiQjTϵi+bitij+Civij+ϵiTPjenci∈Ki(16)t_{ij} \geq\widehat{d}_i\left(\epsilon_i^{\mathsf T}P_j e_n,Q_j^{\mathsf T}\epsilon_i\right) \quad\Longleftrightarrow\quad \begin{cases} \epsilon_i^{\mathsf T}P_j e_n \geq0,\\ A_iQ_j^{\mathsf T}\epsilon_i + b_i t_{ij} + C_i v_{ij} + \epsilon_i^{\mathsf T}P_j e_n c_i \in K_i \end{cases} \tag*{(16)}

for an auxiliary vector vijv_{ij}. All expressions in (16) are affine in (Pj,Qj,tij,vij)(P_j,Q_j,t_{ij},v_{ij}). Hence, this is a standard conic constraint and does not introduce a product among decision variables. For example, under the Euclidean distance, it reduces to the second-order cone constraint

∥QjTϵi−ϵiTPjenai∥2≤tij.\left\lVert Q_j^{\mathsf T}\epsilon_i-\epsilon_i^{\mathsf T}P_j e_n a_i\right\rVert_2 \leq t_{ij}.

For a Mahalanobis distance with factor LL, the left-hand side becomes ∥L(QjTϵi−ϵiTPjenai)∥2\left\lVert L(Q_j^{\mathsf T}\epsilon_i-\epsilon_i^{\mathsf T}P_j e_n a_i)\right\rVert_2. For a polyhedral distance, the corresponding implementation consists only of linear inequalities. Thus, an implementation creates the scalar expression ϵiTPjen\epsilon_i^{\mathsf T}P_j e_n, the vector expression QjTϵiQ_j^{\mathsf T}\epsilon_i, and tijt_{ij}, and submits their joint conic epigraph directly to the conic solver. However, this implementation needs to enforce consistency between the first two expressions, that is, to enforce that Qj=zjxjTQ_j = z_jx_j^{\mathsf T}.

We next use the central observation of mixed-projection conic optimization: a rank restriction can be represented by requiring a matrix to be invariant under a low-rank orthogonal projector Bertsimas et al. [ [3].

Lemma 1. For any W∈Rr×sW \in\mathbb{R}^{r \times s} and k∈[r]k \in[r], Rank⁡(W)≤k\operatorname{Rank}(W) \le k if and only if there exists P∈PkrP \in\mathcal{P}^{r}_{k} such that W=PWW = PW. Furthermore, if P=∑j=1kvjvjTP = \sum_{j=1}^{k} v_jv_j^{T} for orthonormal vectors v1,…,vkv_1,\ldots,v_k, then W=PWW = PW is equivalent to W=∑j=1kvjwjTW = \sum_{j=1}^{k} v_jw_j^{T} for some vectors w1,…,wk∈Rsw_1,\ldots,w_k \in\mathbb{R}^{s}.

Applying this lemma, Qj=zjxjTQ_j = z_jx_j^{T} can be enforced and the following result can be proved.

Theorem 3. The continuous multisource facility location problem is equivalent to

min⁡∑j=1p∑i=1nωitijs.t.∑j=1pPjen=en,tij≥d^i(ϵiTPjen,QjTϵi),i∈[n], j∈[p];Qj=PjQj,j∈[p];Pj∈P1n∩R+n×n,j∈[p].\begin{aligned} \min\quad&\sum_{j=1}^{p}\sum_{i=1}^{n}\omega_i t_{ij} \\ \text{s.t.}\quad&\sum_{j=1}^{p}P_j e_n=e_n,\\ &t_{ij}\ge\widehat{d}_i(\epsilon_i^{T}P_je_n,Q_j^{T}\epsilon_i), && i\in[n],\ j\in[p];\\ &Q_j=P_jQ_j, && j\in[p];\\ &P_j\in\mathcal{P}^{n}_{1}\cap\mathbb{R}^{n\times n}_{+}, && j\in[p]. \end{aligned}

Proof. Given a clustering, construct PjP_j and QjQ_j, as in (13). Each QjQ_j is such that (14) gives a feasible point with the same objective value while satisfying Qj=PjQjQ_j=P_jQ_j, since

PjQj=zjzjTenTzjxjxjT=zjTzjenTzjzjxjT=zjxjT=Qj.P_jQ_j=\frac{z_jz_j^{T}}{e_n^{T}z_j}x_jx_j^{T}=\frac{z_j^{T}z_j}{e_n^{T}z_j}z_jx_j^{T}=z_jx_j^{T}=Q_j.

Conversely, constraints Pj∈P1n∩R+n×nP_j\in\mathcal{P}^{n}_{1}\cap\mathbb{R}^{n\times n}_{+}, together with ∑j=1pPjen=en\sum_{j=1}^{p}P_je_n=e_n, induce the incidence vectors zj=Pjenz_j=P_je_n of a partition of [n][n]. Using the preceding lemma, constraints Qj=PjQjQ_j=P_jQ_j imply Qj=zjxjTQ_j=z_jx_j^{T} for some xj∈Rmx_j\in\mathbb{R}^{m}. Therefore, the conic inequalities reduce to tij≥zijd(ai,xj)t_{ij}\ge z_{ij}d(a_i,x_j), and they are tight at optimality. □

For an aggregated representation, write

P~:=Blockdiag⁡(P1,…,Pp)∈Rpn×pnandQ~:=Blockdiag⁡(Q1,…,Qp)∈Rpn×pm.\widetilde{P}:=\operatorname{Blockdiag}(P_1,\ldots,P_p)\in\mathbb{R}^{pn\times pn}\quad\text{and}\quad\widetilde{Q}:=\operatorname{Blockdiag}(Q_1,\ldots,Q_p)\in\mathbb{R}^{pn\times pm}.

Because of this block structure, it is clear that these aggregated matrices also satisfy Q~=P~Q~\widetilde{Q}=\widetilde{P}\widetilde{Q} while P~∈Pppn\widetilde{P}\in\mathcal{P}^{pn}_{p}.

Corollary 1. The continuous multisource facility location problem is equivalent to the following formulation:

min⁡∑j=1p∑i=1nωitij(LR-A)s.t.∑j=1pPjen=en,Tr⁡(Pj)=1,j∈[p],tij≥d^i(ϵiTPjen,QjTϵi),i∈[n], j∈[p];Q~=P~Q~;P~∈Pppn∩R+pn×pn.\begin{aligned} \min\quad& \sum_{j=1}^{p}\sum_{i=1}^{n}\omega_i t_{ij} && \text{(LR-A)}\\ \text{s.t.}\quad& \sum_{j=1}^{p}P_j e_n=e_n,\\ & \operatorname{Tr}(P_j)=1, && j\in[p],\\ & t_{ij}\ge\widehat{d}_i(\epsilon_i^T P_j e_n,Q_j^T\epsilon_i), && i\in[n],\ j\in[p];\\ & \widetilde{Q}=\widetilde{P}\widetilde{Q};\\ & \widetilde{P}\in\mathcal{P}^{pn}_p\cap\mathbb{R}_{+}^{pn\times pn}. \end{aligned}

Formulation (LR-D) uses one rank-one projector for each facility, whereas this formulation uses one rank-pp projector for the block-diagonal matrix P~\widetilde{P}.

Proof. Equivalence follows from the block structure of P~\widetilde{P} and Q~\widetilde{Q}. We have that Qj=PjQjQ_j=P_jQ_j and, since Tr⁡(Pj)=1\operatorname{Tr}(P_j)=1, each block PjP_j is non-zero and Pj∈P1nP_j\in\mathcal{P}^{n}_1. Then, this formulation is equivalent to (LR-D) and therefore to the continuous multisource facility location problem. □

A third possible low-rank model arises by aggregating the matrices through a sum instead of a diagonal arrangement. Since the zjz_j vectors of a valid assignment are orthogonal, all the information about the assignment is still preserved in this rank pp sum, resulting in a more compact reformulation.

Lemma 2. Let P∈Ppn∩R+n×nP\in\mathcal{P}^{n}_p\cap\mathbb{R}_{+}^{n\times n} satisfy Pen=enPe_n=e_n. Then there is a partition {C1,…,Cp}\{C_1,\ldots,C_p\} of [n][n] with incidence vectors z1,…,zp∈{0,1}nz_1,\ldots,z_p\in\{0,1\}^n such that

P=∑j=1pzjzjTenTzj.P=\sum_{j=1}^{p}\frac{z_jz_j^T}{e_n^Tz_j}.

Proof. The connected components of the positive-entry graph of the nonnegative symmetric matrix PP permit a simultaneous permutation of its rows and columns into irreducible diagonal blocks. Because Pen=enPe_n=e_n and P2=PP^2=P, every block is stochastic and idempotent. Perron–Frobenius theory implies that eigenvalue one is simple in each block, while idempotency implies that every eigenvalue is zero or one. Thus, every block has rank one and, by symmetry and stochasticity, equals ∣C∣−1e∣C∣e∣C∣T|C|^{-1}e_{|C|}e_{|C|}^T on its index set CC. After undoing the permutation, this block is zzT/(enTz)zz^T/(e_n^Tz), where zz is the incidence vector of CC. Finally, Rank⁡(P)=p\operatorname{Rank}(P)=p implies that there are exactly pp blocks. □

Theorem 4. The following formulation is equivalent to the continuous multisource facility location problem:

min⁡∑i=1nωiti(LR-SA)s.t.ti≥d(ai,QTϵi),i∈[n];Pen=en,Q=PQ,P∈Ppn∩R+n×n, Q∈Rn×m.\begin{aligned} \min\quad& \sum_{i=1}^{n}\omega_i t_i && \text{(LR-SA)}\\ \text{s.t.}\quad& t_i\ge d(a_i,Q^T\epsilon_i), && i\in[n];\\ & Pe_n=e_n,\\ & Q=PQ,\\ & P\in\mathcal{P}^{n}_p\cap\mathbb{R}_{+}^{n\times n},\ Q\in\mathbb{R}^{n\times m}. \end{aligned}

Proof. Given a clustering, construct the matrices PjP_j and QjQ_j as before and choose P=∑j=1pPjP = \sum_{j=1}^{p} P_j and Q=∑j=1pQjQ = \sum_{j=1}^{p} Q_j. Such a choice has P∈Pnp∩R+n×nP \in\mathcal{P}_{n}^{p} \cap\mathbb{R}_{+}^{n \times n}. Since vectors zjz_j are pairwise orthogonal, we have that

PQ=∑j,j′=1pPjQj′=∑j=1pzjzjTenTzjzjxjT=∑j=1pzjTzjenTzjzjxjT=∑j=1pQj=Q.PQ = \sum_{j,j'=1}^{p} P_jQ_{j'} = \sum_{j=1}^{p} \frac{z_jz_j^T}{e_n^Tz_j} z_jx_j^T = \sum_{j=1}^{p} \frac{z_j^Tz_j}{e_n^Tz_j} z_jx_j^T = \sum_{j=1}^{p} Q_j = Q.

Furthermore, QTϵi=∑j=1pQjTϵi=∑j=1pxjzjTϵi=∑j=1pzijxjQ^T\epsilon_i = \sum_{j=1}^{p} Q_j^T\epsilon_i = \sum_{j=1}^{p} x_jz_j^T\epsilon_i = \sum_{j=1}^{p} z_{ij}x_j, that is, QTϵiQ^T\epsilon_i is the center assigned to aia_i. Therefore, this construction gives a feasible solution with the same objective value, and the inequalities ti≥d(ai,QTϵi)t_i \ge d(a_i,Q^T\epsilon_i) are tight at optimality.

Conversely, given any feasible matrices PP and QQ of this formulation, Lemma 2 gives P=∑j=1pzjzjT/(enTzj)P = \sum_{j=1}^{p} z_jz_j^T/(e_n^Tz_j) for the incidence vectors of a partition. Lemma 1 assures QQ is of the form Q=∑j=1pQj=∑j=1pzjxjTQ = \sum_{j=1}^{p} Q_j = \sum_{j=1}^{p} z_jx_j^T for some vectors xj∈Rmx_j \in\mathbb{R}^{m}. Again, QTϵi=∑j=1pzijxjQ^T\epsilon_i = \sum_{j=1}^{p} z_{ij}x_j will act as the center assigned to aia_i and constraints ti≥d(ai,QTϵi)t_i \ge d(a_i,Q^T\epsilon_i) will be tight at optimality, proving the equivalence of the problems. □

Once the projectors are fixed, all remaining constraints in these models are conic. Thus, the assignment decisions of the original big-MM model have been replaced by orthogonal projection matrices.

Remark 2. Related semidefinite and conic decomposition techniques are discussed in Bertsimas and Cory-Wright [ [2], Coey et al. [ [18], Vandenberghe and Boyd [ [43]. In fact, the assignment matrices PP and the center matrices QQ in the above three formulations play the same role as matrices YY and XX respectively in the framework described in Bertsimas and Cory-Wright [ [2].

Furthermore, it is of note how well projection matrices seem to be suited to the role of assignment variables, particularly in the context of clustering and facility location problems. The earlier work of Peng and Xia Peng and Xia [ [39] on semidefinite formulations for kk-means-type problems already hinted at this interplay.

Exact Outer Approximations

We close the section with a globally exact method for the disaggregated model (LR-D). The method follows the outer-approximation strategy for MPCO in Bertsimas et al. [ [3]. A global projector master selects the partition structure, while conic subproblems evaluate the location decisions and generate supporting cuts. The same construction can be applied to the sum-aggregated formulation (LR-SA). We first present the disaggregated version and then state its sum-aggregated counterpart.

Let C\mathcal{C} collect the conic constraints in (LR-D) involving (P,Q,T)(P,Q,T), excluding Qj=PjQjQ_j = P_jQ_j. For P=(P1,…,Pp)∈Pn,pP = (P_1,\ldots,P_p) \in\mathcal{P}^{n,p}, define the fixed-projector value:

h(P):=min⁡Q,T{∑j=1p∑i=1nωitij:(P,Q,T)∈C, Qj=PjQj, j∈[p]}.(17)h(P) := \min_{Q,T} \left\{ \sum_{j=1}^{p}\sum_{i=1}^{n} \omega_i t_{ij} : (P,Q,T) \in\mathcal{C},\ Q_j = P_jQ_j,\ j \in[p] \right\}. \tag*{(17)}

The subproblem is conic for fixed PP and can be solved with any suitable conic optimization solver. It contains neither binary variables nor big-MM convexifications.

Since h(P)≥0h(P) \ge0, the projector-space logic gives

θ≥h(Pˉ)(1−ΔPˉ(P))(18)\theta\ge h(\bar{P})\left(1-\Delta_{\bar{P}}(P)\right) \tag*{(18)}

is valid (recall Δ\Delta as (10)). Because (8) contains only partition projectors and every such projector has a conic completion, no feasibility cuts or artificial bounds are required.

After rr evaluations, the master problem reads

min⁡P∈Pn,p, θ≥0θs.t.θ≥h(Pℓ)(1−ΔPℓ(P)),∀ℓ∈[r].\begin{aligned} \min_{P\in\mathcal{P}^{n,p},\,\theta\geq0}\quad&\theta\\ \text{s.t.}\quad&\theta\geq h(P_\ell)\left(1-\Delta_{P_\ell}(P)\right),\quad\forall\ell\in[r]. \end{aligned}

Notice that, just as with g(P)g(P), we can exploit the facility-wise separability of h(P)h(P) to generate cuts, as described in (12).

The same facility-disaggregated master applies to (LR-A), because its block-diagonal construction preserves the separability of the fixed-projector subproblem. Its block-diagonal PSD constraint is equivalently represented by a collection of facility-wise PSD blocks. The master may be solved with the rank-one projector factorization, as in Bertsimas et al. [ [3]. Alternatively, a master solver may use the equivalent incidence representation zj=Pjenz_j=P_je_n for the finite projector set and reconstruct Pj=zjzjT/(enTzj)P_j=z_jz_j^{T}/(e_n^{T}z_j) at every incumbent. A conic solver then evaluates (17), and (18) is returned to the master. The incidence vectors are only an exact encoding of the partition projectors in the master. They are not coupled to distances and introduce no big-MM inequalities.

Algorithm 1 Outer Approximation for (LR-D)

Require: Initial P1∈Pn,pP_1\in\mathcal{P}^{n,p}, tolerance ε>0\varepsilon>0.

  1. Set r←1r\leftarrow1, LB←−∞\mathrm{LB}\leftarrow-\infty, and UB←+∞\mathrm{UB}\leftarrow+\infty.

  2. repeat

  3. Solve (17) at PrP_r with a conic solver and obtain h(Pr)h(P_r).

  4. Add (18) and set UB←min⁡{UB,h(Pr)}\mathrm{UB}\leftarrow\min\{\mathrm{UB},h(P_r)\}.

  5. Solve the master problem (LR-D-LBr_r) globally; let (Pr+1,θr+1)(P_{r+1},\theta_{r+1}) be an optimal solution.

  6. Set LB←θr+1\mathrm{LB}\leftarrow\theta_{r+1} and r←r+1r\leftarrow r+1.

  7. until UB−LB≤ε\mathrm{UB}-\mathrm{LB}\leq\varepsilon

  8. return The best feasible projector and its associated clustering solution.

Every master value is a valid lower bound because all cuts underestimate hh, whereas every fixed-projector value is the objective of a feasible clustering and therefore an upper bound. Algorithm 1 consequently maintains a valid optimality gap.

Theorem 5. If every fixed-projector subproblem is solved exactly and the master problem is solved globally at every iteration, then Algorithm 1 terminates after finitely many iterations with a globally optimal solution of (LR-D).

Proof. Cut (18) reproduces the exact value at its evaluated projector and has a nonpositive right-hand side at every other labeled partition. Hence, every master value is a valid lower bound and every fixed-projector value is an upper bound. The set Pn,p\mathcal{P}^{n,p} is finite. Each iteration either closes the optimality gap or evaluates a new projector. Finite termination follows. □

For formulation (LR-SA), let

PSAn,p:={P∈Ppn∩R+n×n:Pen=en}.\mathcal{P}_{\mathrm{SA}}^{n,p}:=\left\{P\in\mathcal{P}^{n}_{p}\cap\mathbb{R}_{+}^{n\times n}:Pe_n=e_n\right\}.

This finite set represents the feasible partitions without distinguishing their facility labels. For a fixed P∈PSAn,pP\in\mathcal{P}_{\mathrm{SA}}^{n,p}, define

h~(P):=min⁡Q,t{∑i=1nωiti:ti≥d(ai,QTei), i∈[n], Q=PQ}.\widetilde{h}(P):=\min_{Q,t}\left\{\sum_{i=1}^{n}\omega_i t_i:t_i\geq d(a_i,Q^{T}e_i),\ i\in[n],\ Q=PQ\right\}.

For P∈PSAn,pP \in\mathcal{P}_{\mathrm{SA}}^{n,p}, write cih(P)=1c_{ih}(P)=1 if Pih>0P_{ih}>0, and zero otherwise. Thus, cih(P)c_{ih}(P) indicates whether ii and hh are in the same cluster. For an evaluated projector P‾\overline{P}, define

ΔP‾(P):=∑i<h:cih(P‾)=1(1−cih(P))+∑i<h:cih(P‾)=0cih(P).\Delta_{\overline{P}}(P):=\sum_{i<h:c_{ih}(\overline{P})=1}(1-c_{ih}(P))+\sum_{i<h:c_{ih}(\overline{P})=0}c_{ih}(P).

This label-invariant quantity is zero if P=P‾P=\overline{P} and at least one otherwise. Since h~(P‾)≥0\widetilde{h}(\overline{P})\geq0, the corresponding logic cut is

θ≥h~(P‾)(1−ΔP‾(P)).\theta\geq\widetilde{h}(\overline{P})(1-\Delta_{\overline{P}}(P)).

It is exact at P‾\overline{P} and otherwise is dominated by θ≥0\theta\geq0. In the discrete master, cih(P)c_{ih}(P) is a binary coassignment variable. After evaluating P1,…,PrP_1,\ldots,P_r, the master reads

min⁡P∈PSAn,p, θ≥0θs.t.θ≥h~(Pℓ)(1−ΔPℓ(P)),ℓ∈[r].\begin{aligned} \min_{P\in\mathcal{P}_{\mathrm{SA}}^{n,p},\,\theta\geq0}\quad&\theta\\ \text{s.t.}\quad&\theta\geq\widetilde{h}(P_\ell)(1-\Delta_{P_\ell}(P)),\quad\ell\in[r]. \end{aligned}

Note that if the fixed-projector subproblems and the master problems are solved exactly, Algorithm 1, with PP and hh replaced by PP and h~\widetilde{h}, terminates finitely with a globally optimal solution of (LR-SA).

Indeed, each iteration either closes the optimality gap or evaluates a new member of the finite set PSAn,p\mathcal{P}_{\mathrm{SA}}^{n,p}. This variant uses one rank-pp projector and removes the symmetry associated with facility labels.

Strengthening and Implementation Strategies

The exact decomposition methods can be strengthened at two different levels. Valid inequalities and semidefinite bounds improve the lower approximation represented by the discrete master. Warm starts and the management of the master–subproblem interaction improve the practical execution without changing the exactness of the methods. We present these two levels separately.

Valid Inequalities and Relaxation Strengthening

We first collect the inequalities that are valid for every feasible projector. They can be imposed independently of the initialization and of the sequence of partitions generated by the algorithms, and they strengthen both the root relaxation and the subsequent master problems.

Semidefinite Projection Bound. Define the weighted distance matrix

Dikω:=min⁡{ωi,ωk}d(ai,ak),i,k∈[n].D_{ik}^{\omega}:=\min\{\omega_i,\omega_k\}d(a_i,a_k),\qquad i,k\in[n].

The triangle inequality implies Dikω≤ωid(ai,x)+ωkd(ak,x)D_{ik}^{\omega}\leq\omega_i d(a_i,x)+\omega_k d(a_k,x) for every xx. Replacing Y(xj)Y(x_j) by DωD^\omega and relaxing idempotency gives the disaggregated relaxation

min⁡P1,…,Pp12∑j=1p⟨Dω,Pj⟩s.t.∑j=1pPjen=en,Tr⁡(Pj)=1,∀j∈[p],Pj⪰0,Pj≥0,∀j∈[p].\begin{aligned} \min_{P_1,\ldots,P_p}\quad&\frac{1}{2}\sum_{j=1}^{p}\langle D^\omega,P_j\rangle\\ \text{s.t.}\quad&\sum_{j=1}^{p}P_j e_n=e_n,\\ &\operatorname{Tr}(P_j)=1,\qquad\forall j\in[p],\\ &P_j\succeq0,\quad P_j\geq0,\qquad\forall j\in[p]. \end{aligned}

(SDP-RELAX-D)

Every feasible solution of (SDP-RELAX-D) yields an aggregate matrix P=∑jPjP = \sum_{j} P_j. Dropping the requirement that PP admit this facility-wise decomposition gives the lighter relaxation

min⁡P⪰0,  P≥012⟨Dω,P⟩s.t.Pen=en,Tr⁡(P)=p,\begin{aligned} \min_{P \succeq0,\;P \ge0}\quad& \frac{1}{2}\langle D^\omega,P\rangle\\ \text{s.t.}\quad& Pe_n=e_n,\\ & \operatorname{Tr}(P)=p, \end{aligned}

Both convex models provide valid lower bounds. The disaggregated model also provides facility-wise fractional assignment scores for rounding. Semidefinite relaxations and rounding are well-established tools for partition problems Goemans [ [27], Luo et al. [ [36], Peng and Wei [ [38].

Projection Inequalities. For the aggregate partition projector P=∑j=1pPjP = \sum_{j=1}^{p} P_j, one has Pih=∣C∣−1P_{ih} = |C|^{-1} whenever points ii and hh belong to the same cluster CC, and Pih=0P_{ih} = 0 otherwise. In particular, Pih≤PiiP_{ih} \le P_{ii} states that the normalized association between two points cannot exceed the diagonal value of the cluster containing ii. The inequalities

Pih+Pik≤Pii+Phk,i,h,k∈[n],P_{ih} + P_{ik} \le P_{ii} + P_{hk}, \qquad i,h,k \in[n],

provide a normalized transitivity condition. For example, if ii is associated with both hh and kk, then hh and kk must also be associated. Both families are satisfied by every partition projector and exclude fractional eigenvalues admitted by the basic doubly nonnegative relaxation. They cannot be imposed directly on the MICO formulation using only the zz-variables, because Pih=∑j=1pzijzhj/(∑ℓ=1nzℓj)P_{ih} = \sum_{j=1}^{p} z_{ij}z_{hj}/(\sum_{\ell=1}^{n} z_{\ell j}) involves binary products and the cluster cardinalities. Their direct linear form is therefore a specific advantage of working in the projector space. An equivalent extension of MICO would require additional coassignment and cardinality variables.

Perspective and Trace Bounds. The mixed-projection relaxations can combine distance epigraphs with

(PQQTM)⪰0,\begin{pmatrix} P & Q\\ Q^{T} & M \end{pmatrix} \succeq0,

or the corresponding facility-wise constraints. A valid bound derived from a bounded region containing optimal centers is essential. Let aˉ:=1n∑i=1nai\bar{a} := \frac{1}{n}\sum_{i=1}^{n} a_i and translate the demand points by aˉ\bar{a}. Translation does not change the distances or the optimal value. Let X⊆Rm\mathcal{X} \subseteq\mathbb{R}^{m} be any bounded region known to contain an optimal center for every possible nonempty cluster. It is enough to choose

R2≥sup⁡{⟨x−aˉ,x−aˉ⟩:x∈X}.(19)R^2 \ge\sup\{\langle x-\bar{a},x-\bar{a}\rangle: x \in\mathcal{X}\}. \tag*{(19)}

Thus, the validity of the trace bound does not depend on a particular norm or on a particular construction of X\mathcal{X}. At an exact solution, the trace represents the sum of the squared norms of the centers, repeated according to their cluster cardinalities. Since these cardinalities sum to nn, the following bounds are valid:

Tr⁡(M)≤nR2 for (LR-SA) and ∑j=1pTr⁡(Mj)≤nR2 for (LR-D)/(LR-A).\operatorname{Tr}(M) \le nR^2 \text{ for (LR-SA) and } \sum_{j=1}^{p}\operatorname{Tr}(M_j) \le nR^2 \text{ for (LR-D)/(LR-A)}.

These bounds remain valid for the exact formulations and restrict the otherwise weak perspective relaxations.

– Certified SDP Root Bound. Either SDP relaxation can also be used independently of rounding. Let LSDPL_{\mathrm{SDP}} denote a certified lower bound obtained from the selected model. When the SDP is stopped before optimality, LSDPL_{\mathrm{SDP}} must be taken from a dual-feasible solution rather than from the available primal objective. The lower bound requirement θ≥LSDP\theta\ge L_{\mathrm{SDP}} can be imposed in (PW-LBr_r) and (LR-SA-LBr_r). For (LR-D-LBr_r), the corresponding inequality is ∑j=1pθj≥LSDP\sum_{j=1}^{p} \theta_j \ge L_{\mathrm{SDP}}. Hence, the same SDP calculation produces an initial partition and strengthens the root lower bound.

– Projector Distance Bounds. The distance lower bound can be imposed directly in the projection space, without introducing assignment or coassignment variables. For every feasible cluster projector PjP_j and every facility location xjx_j, the triangle inequality gives

⟨Dω,Pj⟩≤⟨Y(xj),Pj⟩.\langle D^\omega, P_j\rangle\le\langle Y(x_j), P_j\rangle.

Consequently, the pairwise master (PW-LBr_r) can be strengthened with

θ≥12∑j=1p⟨Dω,Pj⟩.\theta\ge\frac{1}{2}\sum_{j=1}^{p}\langle D^\omega, P_j\rangle.

This inequality is linear in the projector entries. Minimizing it over the doubly nonnegative relaxation of Pn,p\mathcal{P}^{n,p} gives (SDP-RELAX). Thus, this SDP is the natural relaxation of the projector bound above, rather than a bound imported from (MICO). The same argument applies to the low-rank models. The disaggregated master program (LR-D-LBr_r) with epigraph variables θj\theta_j can use the projection inequalities

θj≥12⟨Dω,Pj⟩,j∈[p].\theta_j \ge\frac{1}{2}\langle D^\omega, P_j\rangle,\qquad j\in[p].

For the aggregated formulation, the right-hand sides are summed over the diagonal projector blocks. These bounds complement the dual supporting cuts (18). The former use the geometry of pairwise distances, while the latter use the complete fixed-projector conic subproblem. Both families are expressed solely through the projection variables that define the formulations.

– Symmetry Breaking. Finally, the interchangeability of facility labels creates equivalent partitions. One may use the following inexpensive conditions to partially break this symmetry. If demand point ii is not assigned to one of facilities 1,…,i−11,\ldots,i-1, then it is assigned to facility ii. In terms of the assignment variables, this implication is

zii≥1−∑j=1i−1zij.z_{ii} \ge1-\sum_{j=1}^{i-1}z_{ij}.

Since every demand point is assigned to exactly one facility, the above set of constraints is equivalently written as ∑j=1izij=1\sum_{j=1}^{i}z_{ij}=1 for i∈[p]i\in[p]. In particular, it implies z11=1z_{11}=1 and prevents demand point ii from using a facility with label larger than ii.

For the projector-based formulations, zij=ϵiTPjenz_{ij}=\epsilon_i^{T}P_je_n. Therefore, the same conditions can be imposed directly on the projectors as

∑j=1iϵiTPjen=1,i∈[p].\sum_{j=1}^{i}\epsilon_i^{T}P_je_n=1,\qquad i\in[p].

Every unlabeled nonempty partition has a labeling satisfying these conditions, for example by ordering its clusters according to the first demand point appearing in each cluster. Consequently, the conditions do not change the optimal value. They remove part, but not necessarily all, of the facility-label symmetry. Their main advantage is that they add only pp linear constraints and require no auxiliary variables. A warm-start partition can be relabeled by first appearance before it is passed to the master. A stronger option is the complete first-occurrence ordering

zij≤∑h=1i−1zh,j−1,i∈[n],j=2,…,p.z_{ij} \le\sum_{h=1}^{i-1} z_{h,j-1}, \qquad i \in[n], \qquad j=2,\ldots,p.

or, equivalently, ϵiTPjen≤∑h=1i−1ϵhTPj−1en\epsilon_i^T P_j e_n \le\sum_{h=1}^{i-1}\epsilon_h^T P_{j-1}e_n. This selects the representative in which clusters are ordered by their first demand point and removes the remaining facility-label symmetry from the labeled masters.

Warm Starts and Algorithmic Implementation

The preceding inequalities improve lower bounds. We now describe how feasible solutions are initialized and how the exact master–subproblem decompositions are executed. These choices affect computational performance but do not replace the lower-bound certificates required for exactness.

The exact methods developed in § 3 and § 4 can start from any feasible nonempty partition. Their performance, however, depends strongly on the quality of the initial incumbent. A good partition provides an early upper bound, guides the search toward promising projector configurations, and may reduce the number of conic subproblems evaluated before the optimality gap closes. Warm starts are particularly useful because the assignment and location decisions reinforce each other.

This observation is the basis of classical location-allocation heuristics and their modern variants Bongartz et al. [1994], Brimberg et al. [2000], Cooper [1964]. It also motivates the use of several starting configurations rather than a single deterministic initialization Drezner and Brimberg [2026]. Warm starts produce feasible solutions and upper bounds only. Global optimality is still certified by the exact methods.

  • Multiple Starting Partitions. Candidate facility locations can be selected from the demand points or from geometrically dispersed subsets of them. Each demand point is assigned to a closest candidate facility, with empty facilities repaired by moving demand points from non-singleton clusters. The resulting partitions provide a diverse collection of inexpensive initial solutions. This option follows the general multistart principle used in multifacility location Cooper [1964], Drezner and Brimberg [2026].

  • Alternating Location and Allocation. Starting from a feasible partition, fix its projectors. Problem (PW) then separates into the pp single-facility problems

min⁡xj∈Rm12⟨Pj,Y(xj)⟩,j∈[p].\min_{x_j \in\mathbb{R}^m} \frac{1}{2}\langle P_j,Y(x_j)\rangle,\qquad j\in[p].

After computing the facility locations, each demand point is reassigned to a closest facility while preserving nonempty clusters. These two steps are repeated until the assignment does not change or the objective improvement is below a tolerance. The objective is nonincreasing and every iterate is feasible. This is the projector version of the classical location–allocation scheme Bongartz et al. [1994], Cooper [1963, 1964]. The single-facility problems can be handled by any suitable conic solver. The allocation update assigns each point directly to a closest facility, with a repair step if a cluster becomes empty.

  • SDP Rounding. Let (P1⋆,…,Pp⋆)(P_1^\star,\ldots,P_p^\star) solve (SDP-RELAX-D), and define the fractional score matrix Λ∈Rn×p\Lambda\in\mathbb{R}^{n\times p} by λij:=ϵiTPj⋆en\lambda_{ij}:=\epsilon_i^T P_j^\star e_n. A nonempty partition is recovered from

max⁡Z∈{0,1}n×p{⟨Λ,Z⟩:Zep=en, ZTen≥ep}.\max_{Z\in\{0,1\}^{n\times p}}\{\langle\Lambda,Z\rangle: Ze_p=e_n,\ Z^T e_n\ge e_p\}.

The rounded partition is refined by alternating location and allocation. Its objective value initializes the upper bound, its projectors initialize the exact master problem, and the SDP value remains available as an independent lower bound.

Certified Subproblem Values and Cut Management. For a partition proposed by the discrete master, a conic solver handles the associated convex location subproblems. A feasible center and its primal cost give a valid solution and can update the incumbent. In contrast, only a dual-feasible objective is used as a certified lower value. If L(C)L(C) is the dual bound obtained for a cluster CC, one may cache this value and add, for every facility label jj, the valid cut

θj≥L(C)(∑i∈Czij−∣C∣+1).\theta_j \ge L(C)\left(\sum_{i\in C} z_{ij} - |C| + 1\right).

The cut is active when facility jj contains all points of CC. The certified values of all clusters in the current partition are also combined in a logic-based optimality cut that excludes repeating that projector without accounting for its certified cost. Such a cache permits both cut types to be reused for other facility labels and later partitions. If the conic solver returns a primal feasible center but no dual-feasible bound, the primal value may still improve the incumbent, but it is never used on the right-hand side of a lower-bounding cut. If a certificate required by the exact step is missing, the evaluation remains unresolved and the algorithm reports a subproblem limit instead of claiming global optimality.

The strategies described above can be combined in different ways. § 6 specifies the configuration adopted for each formulation in our computational study.

Numerical Experiments

This section compares the exact formulations and studies whether the projection models improve the lower bounds and the final optimality gaps. We report solution time together with the percentage of unsolved instances, since a smaller time caused by early termination must not be interpreted as better performance.

Instances and Setting

We use the planar Eilon instances Eilon et al. [ [25], available in the repository Blanco and Gázquez [ [4]. The test set contains five instances for each n∈{10,20,30,40}n \in\{10,20,30,40\}, as well as the complete instance for n=50n = 50. We consider p∈{2,3,5}p \in\{2,3,5\} facilities in three different ℓτ\ell_\tau metric spaces, with τ∈{3/2,2,3}\tau\in\{3/2,2,3\}. We compare the big-MM integer conic formulation, denoted by MICO, the pairwise model PW, and the disaggregated, aggregated, and sum-aggregated low-rank models LR-D, LR-A, and LR-SA. Gurobi 13.0.1 solves MICO and the discrete masters, while MOSEK 11.0.29 solves the SDP relaxations and conic subproblems. The experiments were run on a 2022 Mac Studio with an Apple M1 Max processor, 64 GB of memory, and macOS Tahoe 26.6.2. The time limit was 3600 seconds, the root SDP was limited to 300 seconds, and the relative optimality tolerance was 10−410^{-4}. For every instance, the common warm start is computed once before the five methods are called, so its construction time is not included in their individual runtimes. The reported time of each projection method includes its method-specific root SDP, the strengthened Gurobi master, and all subsequent MOSEK cluster evaluations. The code, processed instances, complete run-level results, and scripts used to generate the tables and figures are available in the associated repository Blanco et al. [ [11].

All methods use the best warm start from ten initial partitions, alternating location-allocation, and SDP rounding, together with the SDP lower bound and prefix symmetry.

The projection models also use complete ordering, projection inequalities, geometric and subset cuts, and dual-certified cuts. PW uses the pairwise relaxation. LR-D and LR-A use facility-wise perspectives and the aggregate trace bound, while LR-SA uses one aggregated perspective and trace bound. These are the complete strategies of § 5. For the trace bounds: if τ=2\tau= 2 we choose R2R^2 as (19) for X={ai}i∈[n]\mathcal{X} = \{a_i\}_{i\in[n]}. In this case, the convex hull of the demand points is contained in the corresponding Euclidean ball. For τ∈{3/2,3}\tau\in\{3/2,3\}, we use R2=∑r=1m(max⁡1≤i≤n∣air−aˉr∣)2R^2 = \sum_{r=1}^{m}(\max_{1\le i\le n}|a_{ir}-\bar{a}_r|)^2. This is the squared radius of the coordinate-wise box containing the centered demand points. These regions contain an optimal center for every cluster and therefore satisfy the general validity condition stated in § 5. In the Gurobi masters, the labeled methods use one epigraph variable per facility and the reusable subset cuts described above. Formulation LR-SA keeps a canonical incidence encoding only to construct its master constraints, while its partition logic cut is written in the label-invariant coassignment variables. The projector methods use the incidence representation in the master and reconstruct the corresponding projector at each incumbent. We use an explicit solve-separate-resolve loop: Gurobi solves the master, MOSEK certifies the fixed-partition conic subproblems, and the resulting cuts are added before the master is solved again.

The numerical study reports both primal and dual effects of these strategies. For each formulation, we record the best feasible value, the initial continuous-relaxation bound, the SDP bound, the final certified lower bound, and the computing time required by each component. Relaxation quality is measured by

U−Lmax⁡{1,∣U∣},\frac{U-L}{\max\{1,|U|\}},

where UU is the best feasible value and LL is the bound under comparison. For every method, LL is the continuous relaxation of the strengthened implemented master after adding its symmetry constraints and the available certified SDP root bound. For the projector methods, the method-specific SDP bound is also stored separately. Thus, the reported continuous-relaxation gap compares the implemented strengthened masters, rather than the raw continuous relaxations of the algebraic formulations. This distinction allows us to assess whether an improvement comes from a better feasible solution or from a stronger lower bound.

Computational Results

Table 1 reports averages over the common runs available for all five methods. Runtime, final optimality gap, and percentage of unsolved instances are displayed in separate blocks. The best value of each measure for every (n,τ)(n,\tau) is in bold. A run is classified as unsolved when the corresponding method does not certify optimality within the one-hour limit. Only runs available for every method are included, so all entries within an (n,τ)(n,\tau) row are based on the same instances. All methods solve the n=10n=10 instances in about two seconds on average. For n=20n=20, formulations PW, LR-D, and LR-A solve every run, with PW requiring only 202.4–242.7 seconds. Formulation MICO leaves 13.3%–40.0% unsolved, while the rate for LR-SA is 6.7%–20.0%. At n=30n=30, MICO certifies one more run than PW, LR-D, and LR-A, but their average gaps are only 17.0%–20.4%, compared with 23.5%–24.1% for MICO. For n=40n=40, PW, LR-D, and LR-A each certify one run for τ=3/2\tau= 3/2, and no method certifies a run for τ∈{2,3}\tau\in\{2,3\}. Formulation LR-A gives the smallest gap for τ=3/2\tau= 3/2, and PW for τ∈{2,3}\tau\in\{2,3\}. At n=50n=50, all runs reach the time limit and PW gives the smallest gap for every norm. Hence, the main benefit on the largest instances is a stronger final certificate rather than a shorter runtime. In Figure 1, the horizontal value qq is the runtime relative to the fastest proof of optimality, and the profile gives the fraction solved within this factor. Formulation PW dominates for small qq and reaches its final optimality rate much earlier. Formulations PW, LR-D, and LR-A attain the same final optimality rate, but LR-D and LR-A require larger runtime factors, while MICO and LR-SA prove optimality for a smaller fraction of the instances. Thus, PW gives the best balance between speed and the ability to prove optimality.

Performance profiles over all matched instances and tested sizes

Figure 1. Performance profiles over all matched instances and tested sizes.

nnτ\tauTime (s) MICOPWLR-DLR-ALR-SAOpt. Gap (%) MICOPWLR-DLR-ALR-SAUnsolved (%) MICOPWLR-DLR-ALR-SA
103/23/21.10.92.01.91.40.00.00.00.00.00.00.00.00.00.00.0
20.40.61.21.11.00.00.00.00.00.00.00.00.00.00.00.0
31.20.82.01.81.40.00.00.00.00.00.00.00.00.00.00.0
203/23/21454.2200.4258.0284.21094.58.50.00.00.00.240.00.00.00.00.013.3
2869.2241.5270.0263.71201.52.50.00.00.00.113.30.00.00.00.06.7
31436.7242.7269.8245.51191.39.70.00.00.00.233.30.00.00.00.020.0
303/23/22905.92745.22778.02775.13117.624.117.018.717.222.466.773.373.373.373.3
22581.42796.02830.72818.23228.023.519.018.920.422.566.773.373.373.386.7
32941.92818.12830.92846.73286.223.917.917.417.322.166.773.373.373.380.0
403/23/23600.03558.03553.13598.53600.034.823.123.022.926.6100.093.393.393.3100.0
23600.03600.03600.03600.03600.033.324.825.025.027.9100.0100.0100.0100.0100.0
33600.03600.03600.03600.03600.034.823.623.923.727.1100.0100.0100.0100.0100.0
503/23/23600.03600.03600.03600.03600.035.728.031.129.832.5100.0100.0100.0100.0100.0
23600.03600.03600.03600.03600.035.630.735.533.734.9100.0100.0100.0100.0100.0
33600.03600.03600.03600.03600.035.428.730.530.634.3100.0100.0100.0100.0100.0

Table 1. Average runtime, final optimality gap, and percentage of unsolved instances. Boldfaced values indicate the best performance within each (n,τ)(n,\tau) group (except those reaching timelimit for all instances or 100% final GAP).

Figure 2 helps explain these computational differences. The left panel counts the two cut families recorded in the experiment files. Cached subset cuts and the static geometric master constraints are not included. Formulations LR-D and LR-A generate close to 400 recorded cuts at n=30n = 30. Their sharp decline at n=50n = 50 reflects the higher cost of processing the master nodes, which leaves time for fewer master solutions and cuts, not a reduced need for cuts. Formulations PW and LR-SA follow different cut-count patterns. Moreover, PW spends the least time computing SDP bounds. It requires less than 50 seconds through n=40n = 40 and about 140 seconds for n=50n = 50, against approximately 300 seconds for the facility-wise models when n≥40n \ge40. Thus, the pairwise formulation combines effective cuts with cheaper SDP computations, consistently with its runtime and final-gap results.

Average number of partition-logic and separated SDP triangle cuts generated by the projection formulations and average time spent computing SDP bounds

Figure 2. Average number of partition-logic and separated SDP triangle cuts generated by the projection formulations (left) and average time spent computing SDP bounds, classified by instance size (right).

Figure 3 focuses on the instances for which MICO does not prove optimality. Let G‾0\overline{G}_0 and G‾m\overline{G}_m denote the average final optimality gaps, in percent, of MICO and projection method mm. The bars report G‾0−G‾m\overline{G}_0-\overline{G}_m in percentage points, so positive values favor the projection method.

Absolute improvement in the average final optimality gap relative to MICO

Figure 3. Absolute improvement, in percentage points, in the average final optimality gap relative to MICO on matched instances not solved to proven optimality by MICO.

All projection formulations reduce the remaining gap. The reductions are similar for n=20n = 20, while the pairwise, disaggregated, and aggregated models are generally strongest for n=30n = 30 and n=40n = 40. For n=50n = 50, PW gives the largest improvement for all three values of τ\tau.

Figure 4 compares the continuous-relaxation LB gap with MICO. If g0g_0 and gmg_m denote their average gaps, the figure reports 100(g0−gm)/g0100(g_0 - g_m)/g_0, so positive values indicate a stronger projection relaxation. The projection relaxations are never weaker than MICO in the matched groups. Formulations LR-D and LR-A give the largest gains at n=30n = 30, while PW and LR-SA are strongest at n=40n = 40. At n=50n = 50, PW remains the strongest. Thus, projection information strengthens the initial lower bounds, although the best formulation depends on the instance size.

Relative improvement of the continuous-relaxation LB gap over MICO

Figure 4. Relative improvement of the continuous-relaxation LB gap over MICO.

Conclusion

This paper represents the assignment structure of continuous multifacility location through orthogonal projectors and conic distance models. The resulting pairwise and three low-rank formulations avoid big-MM constraints, and their exact decompositions strengthen discrete masters with certified conic bounds and cuts. This provides a new framework for understanding the interplay among assignment, location, rank, and semidefinite optimization.

Computationally, the projection formulations generally strengthen the continuous relaxation of the classical integer programs. The pairwise model gives the best overall balance among runtime, final optimality gap, and proven optimality, while the low-rank models are competitive in several groups. These results are promising because SDP technology for exact decomposition is less mature than MILP and MISOCP technology, leaving room for further gains in SDP algorithms, warm starts, and solver interfaces.

Future research includes projector formulations for other assignment-based problems, matrix-completion techniques for cheaper SDP relaxations, extensions to other cones such as the exponential cone, and stronger Benders-type decompositions and certified cuts.

Acknowledgements

The authors gratefully acknowledge financial support from the Agencia Estatal de Investigación of the Ministerio de Ciencia, Innovación y Universidades through grants: PID2024-156594NB-C21, IMAG–MdM CEX2020-001105-M, and IMUS–MdM CEX2024-001517-M.

They also acknowledge funding from the Programa de Andalucía FEDER through project C-EXP-139-UGR23.

References

  1. [1]Amir Beck, Marc Teboulle, and Zahar Chikikshev. Iterative minimization schemes for solving the single source localization problem. SIAM J. Optim., 19(3):1397–1416, 2008.DOI
  2. [2]Dimitris Bertsimas and Ryan Cory-Wright. On polyhedral and second-order cone decompositions of semidefinite optimization problems. Oper. Res. Lett., 48(1):78–85, 2020.DOI
  3. [3]Dimitris Bertsimas, Ryan Cory-Wright, and Jean Pauphilet. Mixed-projection conic optimization: A new paradigm for modeling rank constraints. Oper. Res., 70(6):3321–3344, 2022.DOI
  4. [4]Víctor Blanco and Ricardo Gázquez. MCLPIF: Maximal covering location problem with interconnected facilities. GitHub repository, https://github.com/vblancoOR/mclpif, 2020. Eilon benchmark instances available in the repository.arxiv.org/abs/2005.03274
  5. [5]Víctor Blanco and Miguel Martínez-Antón. On minimal extended representations of generalized power cones. SIAM J. Optim., 34(3):3088–3111, 2024.arxiv.org/abs/2311.10470
  6. [6]Víctor Blanco, Justo Puerto, and Safae El Haj Ben Ali. Revisiting several problems and algorithms in continuous location with ℓτ-norms. Comput. Optim. Appl., 58:563–595, 2014.arxiv.org/abs/1312.7473
  7. [7]Víctor Blanco, Justo Puerto, and Safae El-Haj Ben-Ali. Continuous multifacility ordered median location problems. Eur. J. Oper. Res., 250(1):56–64, 2016.DOI
  8. [8]Víctor Blanco, Justo Puerto, and Diego Ponce. Continuous location under the effect of ‘refraction’. Math. Program., 161:33–72, 2017.DOI
  9. [9]Víctor Blanco, Ricardo Gázquez, Diego Ponce, and Justo Puerto. A branch-and-price approach for the continuous multifacility monotone ordered median problem. Eur. J. Oper. Res., 306(1):105–126, 2023.arxiv.org/abs/2108.00407
  10. [10]Víctor Blanco, Victor Magron, and Miguel Martínez-Antón. On the complexity of p-order cone programs. J. Complex., 91:101979, 2025.arxiv.org/abs/2501.09828
  11. [11]Víctor Blanco, Diego Laborda-Gutiérrez, and Miguel Martínez-Antón. Projectors ContLocation: Code and data for projector-based conic formulations and exact decompositions for continuous multifacility location. https://github.com/vblancoOR/Projectors_ContLocation, 2026.
  12. [12]Rafael Blanquero and Emilio Carrizosa. Continuous location problems and big triangle small triangle: Constructing better bounds. J. Glob. Optim., 45(3):389–402, 2009.DOI
  13. [14]Jack Brimberg, Pierre Hansen, Nenad Mladenović, and Éric D. Taillard. Improvements and comparison of heuristics for solving the uncapacitated multisource Weber problem. Oper. Res., 48(3):444–460, 2000.
  14. [15]Samuel Burer and Renato D C Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program., 95(2):329–357, February 2003.DOI
  15. [16]Samuel Burer and Renato D. C. Monteiro. Local minima and convergence in low-rank semidefinite programming. Math. Program., 103(3):427–444, 2005.DOI
  16. [17]Pey-Chun Chen, Pierre Hansen, Brigitte Jaumard, and Hoang Tuy. Solution of the multisource Weber and conditional Weber problems by D.-C. programming. Oper. Res., 46(4):548–562, 1998.
  17. [18]Chris Coey, Miles Lubin, and Juan Pablo Vielma. Outer approximation with conic certificates for mixed-integer convex problems. Math. Program. Comput., 12:249–293, 2020.DOI
  18. [19]Leon Cooper. Location-allocation problems. Oper. Res., 11(3):331–343, 1963.DOI
  19. [20]Leon Cooper. Heuristic methods for location-allocation problems. SIAM Review, 6(1):37–53, 1964.DOI
  20. [21]Marco Cuturi and Arnaud Doucet. Fast computation of Wasserstein barycenters. In International Conference on Machine Learning, pages 685–693. PMLR, 2014.arxiv.org/abs/1310.4375
  21. [22]Zvi Drezner and Jack Brimberg. Generating appropriate starting configurations for continuous multi-facility location models. IMA J. Manag. Math., 2026.DOI
  22. [24]Zvi Drezner and Atsuo Suzuki. The big triangle small triangle method for the solution of nonconvex facility location problems. Oper. Res., 52(1):128–135, 2004.DOI
  23. [25]Samuel Eilon, Carl D. T. Watson-Gandy, and Nicos Christofides. Distribution Management: Mathematical Modelling and Practical Analysis. Griffin, London, 1971.
  24. [26]Sándor P. Fekete, Joseph S. B. Mitchell, and Karin Beurer. On the continuous Fermat–Weber problem. Oper. Res., 53(1):61–76, 2005.DOI
  25. [27]Michel X Goemans. Semidefinite programming in combinatorial optimization. Math. Program., 79(1):143–161, 1997.DOI
  26. [28]Oktay Günlük and Jeff Linderoth. Perspective reformulations of mixed integer nonlinear programs with indicator variables. Math. Program., 124(1-2):183–205, 2010.
  27. [31]Robert E. Kuenne and Richard M. Soland. Exact and approximate solutions to the multisource Weber problem. Math. Program., 3:193–209, 1972.
  28. [33]Jean B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM J. Optim., 11(3):796–817, 2001.DOI
  29. [34]Alex Lemon, Anthony Man-Cho So, and Yinyu Ye. Low-rank semidefinite programming: Theory and applications. Found. Trends Optim., 2(1–2):1–156, 2016.
  30. [35]Xiaodong Li, Yang Li, Shuyang Ling, Thomas Strohmer, and Ke Wei. When do birds of a feather flock together? k-means, proximity, and conic programming. Math. Program., 179(1):295–341, 2020.
  31. [36]Zhi-Quan Luo, Wing-Kin Ma, Anthony Man-Cho So, Yinyu Ye, and Shuzhong Zhang. Semidefinite relaxation of quadratic optimization problems. IEEE Signal Process. Mag., 27(3):20–34, 2010.
  32. [37]Nimrod Megiddo and Kenneth J. Supowit. On the complexity of some common geometric location problems. SIAM J. Comput., 13(1):182–196, 1984.DOI
  33. [38]Jiming Peng and Yu Wei. Approximating k-means-type clustering via semidefinite programming. SIAM J. Optim., 18(1):186–205, 2007.DOI
  34. [39]Jiming Peng and Yu Wei. A new theoretical framework for k-means-type clustering. In Foundations and Advances in Data Mining, pages 79–96. Springer, 2005.DOI
  35. [40]Antonio M Rodríguez-Chía, Inmaculada Espejo, and Zvi Drezner. On solving the planar k-centrum problem with euclidean distances. Eur. J. Oper. Res., 207(3):1169–1186, 2010.DOI
  36. [41]Kenneth E. Rosing. An optimal method for solving the (generalized) multi-Weber problem. Eur. J. Oper. Res., 58(3):414–426, 1992.DOI
  37. [42]Chuangchuang Sun and Ran Dai. Rank-constrained optimization and its applications. Automatica, 82:128–136, 2017. ISSN 0005-1098.DOI
  38. [43]Lieven Vandenberghe and Stephen Boyd. Semidefinite programming. SIAM Review, 38(1):49–95, 1996.
  39. [44]James E Ward and Richard E Wendell. Using block norms for location modeling. Oper. Res., 33(5):1074–1090, 1985.DOI
  40. [46]Enbo Zhou, Alan T Murray, Jiwon Baik, and Jing Xu. Locating and orienting facilities with anisotropic coverage. Comput. Environ. Urban Syst., 117:102248, 2025.DOI

Paper details

vlnc:W_cfpq9dmb
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents