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 -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 -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 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- 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- 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 -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 . This condition is the matrix version of the binary identity . 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--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 -clustering that replace the assignment-distance products and their associated big- 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 , we write . The vectors of all ones in and the identity matrix in are denoted by and , respectively. Notation stands for the th vector of the canonical basis.
The demand points and facility locations belong to , which is endowed with a metric . We assume that this metric is conic representable. This means that, for every fixed , the epigraph of is the projection of a conic system. Formally, there exist an integer , a proper cone , and an affine map of suitable dimension such that
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 cases. For example, an anisotropic or Mahalanobis distance can be written as
and therefore has a second-order cone representation Ward and Wendell [ [44], Zhou et al. [ [46]. Polyhedral distances of the form
where the vectors define a symmetric and point-separating polytope, are linearly representable by imposing for every 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 , it is the optimal value of the transportation problem
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 , its th column is denoted by , and its entry is denoted by . The superscript denotes transposition, and denotes the trace of a square matrix . Given matrices for , the matrix has the matrices as its diagonal blocks and zeros elsewhere. Its dimension is . The Euclidean and Frobenius inner products are, respectively,
We consider a continuous multisource facility location problem with demand points set , nonnegative weights , and facilities with locations . 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 . The problem is
The binary variable takes value one when demand point is assigned to facility . This gives the mixed-integer nonlinear formulation:
When is induced by an -norm, the products in the objective are usually convexified by combining -order cone constraints with big- envelopes Blanco et al. [ [9, 7]. For rational values of the norm parameter , these -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 . In an epigraph formulation, this gives constraints of the form
and the objective becomes . The constants can be selected separately for each demand point as
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 , its maximum over this convex hull is attained at a demand point, which proves that 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 denote the vector space of real symmetric matrices (). A matrix is a projection matrix if . If, in addition, , then is an orthogonal projection matrix. The eigenvalues of an orthogonal projector satisfy and therefore belong to . Consequently, . We use
for the set of orthogonal projection matrices, and
for the subset of projectors with rank .
Orthogonal projectors provide a matrix representation of linear subspaces. If has rank , then it can be written as
where the columns of form an orthonormal basis of the range of . In particular, every rank-one orthogonal projector has the form for some with . 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 and are nonconvex. A standard semidefinite relaxation replaces idempotency by the spectral constraints together with . It is well-known that these constraints describe the convex hull of orthogonal projectors with rank . Such semidefinite relaxations have been used to represent partitions in -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 be the assignment matrix, and let denote its th column. Since the rows of contain exactly one nonzero entry, different columns have disjoint supports. Thus,
All diagonal entries are positive by (2), so is invertible. We can therefore define
which is the orthogonal projector onto the column space of . This matrix is entrywise nonnegative. Constraint (1) can be written as . Hence, belongs to the column space of , so that . Since all columns of are nonzero and mutually orthogonal, . Therefore, .
The projector can also be disaggregated by facility as
For every , is the rank-one orthogonal projector associated with the demand points assigned to facility . In particular, . 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- constants.
For every , define the symmetric matrix componentwise by
The entry is the total weighted cost of serving demand points and from a same facility located at . Hence, collects all pairwise service costs associated with facility . We obtain
The factor corrects the two occurrences of every individual service cost in . 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:
The assignment vectors of any feasible solution of (PW) are recovered as , . Conversely, every feasible assignment matrix induces feasible projectors through
Both transformations preserve the objective value.
Proof. Let be a feasible assignment matrix. Constraint (2) implies for every , so the matrices in (4) are well defined. Each is entrywise nonnegative, symmetric, idempotent, and has rank one. Also, . It follows from (1) that , and (3) proves that the objective value is preserved.
For the reverse implication, consider a feasible collection in (PW) and set . Nonnegativity and the coupling constraint give and for every . Idempotency and symmetry yield
Consequently,
Every term in the last sum is nonnegative. Therefore, for all and . The linear equality excludes the zero projector, so each induced cluster is nonempty. Finally, a nonnegative rank-one projector whose row-sum vector is must satisfy . Applying (3) completes the proof. □
We next express (PW) in the value-function form used in mixed-projection conic optimization. Define the epigraph set
and let be its extended-valued indicator function. Thus, when and otherwise. Since the metric 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 , consider the extended-valued function
The matrix isolates the nonconvexity stemming from the product between the projector and the epigraph variable. For fixed , the equality is linear, so (6) is a conic optimization problem.
Theorem 2. For every ,
Consequently, is equivalent to
In particular, separates the discrete partition structure, represented by the projectors, from the location conic subproblems represented by .
Proof. Fix . Eliminating from (6) gives
where the latter equality follows because and are symmetric. For any , the matrix is entrywise nonnegative. Since is also entrywise nonnegative,
Equality is attained by choosing . Taking the infimum over proves (7). Substitution of this identity in proves the equivalence.
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
By Theorem 1, is precisely the set of labeled nonempty partitions represented through orthogonal projectors. For a fixed projector collection , define the location subproblem value
The equality follows from (7). Thus, is obtained by solving independent conic programs.
To construct a master problem, consider an evaluated projector collection , set , and define
For , the vector is the binary incidence vector of cluster . Consequently, if and represent the same labeled partition, whereas for every different labeled partition. Since , the logic-based optimality cut
is valid over . It imposes the exact location cost at and becomes redundant at every other labeled partition. After evaluating the projector collections , the master problem is
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 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 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 (9). It introduces variables , imposes , and minimizes . Let represent the cluster of demand points induced by a previously evaluated rank-one projector . If denotes a dual-certified value for the single-facility problem , it adds
This inequality remains valid when facility contains , 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 . 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
For an assignment matrix consider the extended-valued function
Now, the matrix isolates the product between binary variables and the continuous epigraph variables. For fixed , the equality is linear, so is a conic optimization problem which serves as a tractable subproblem in the decomposition scheme. It is not difficult to see that
is equivalent to (MICO). Hence, we can add the logic-based optimality cuts
provided by the subproblem evaluated at a fixed assignment 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 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- 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- envelopes.
Given a feasible assignment and its centers, define
The active distance can be written using only and . For this purpose, let and denote its recession function by . We define the closed perspective of as
This definition depends only on the arguments and does not involve an assignment variable. In particular, and . For a feasible assignment, and . Therefore,
In formulations (LR-D), and (LR-A), the two arguments of are the decision expressions and . Thus, neither nor is a decision variable in these models. They are used only in (14) to prove equivalence with the original formulation. The epigraph of is obtained by homogenizing an epigraph representation of , and is therefore conic representable whenever the epigraph of is conic representable Günlük and Linderoth [ [28].
More specifically, suppose that a conic representation of is
Homogenizing (15) gives
for an auxiliary vector . All expressions in (16) are affine in . 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
For a Mahalanobis distance with factor , the left-hand side becomes . For a polyhedral distance, the corresponding implementation consists only of linear inequalities. Thus, an implementation creates the scalar expression , the vector expression , and , 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 .
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 and , if and only if there exists such that . Furthermore, if for orthonormal vectors , then is equivalent to for some vectors .
Applying this lemma, can be enforced and the following result can be proved.
Theorem 3. The continuous multisource facility location problem is equivalent to
Proof. Given a clustering, construct and , as in (13). Each is such that (14) gives a feasible point with the same objective value while satisfying , since
Conversely, constraints , together with , induce the incidence vectors of a partition of . Using the preceding lemma, constraints imply for some . Therefore, the conic inequalities reduce to , and they are tight at optimality. □
For an aggregated representation, write
Because of this block structure, it is clear that these aggregated matrices also satisfy while .
Corollary 1. The continuous multisource facility location problem is equivalent to the following formulation:
Formulation (LR-D) uses one rank-one projector for each facility, whereas this formulation uses one rank- projector for the block-diagonal matrix .
Proof. Equivalence follows from the block structure of and . We have that and, since , each block is non-zero and . 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 vectors of a valid assignment are orthogonal, all the information about the assignment is still preserved in this rank sum, resulting in a more compact reformulation.
Lemma 2. Let satisfy . Then there is a partition of with incidence vectors such that
Proof. The connected components of the positive-entry graph of the nonnegative symmetric matrix permit a simultaneous permutation of its rows and columns into irreducible diagonal blocks. Because and , 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 on its index set . After undoing the permutation, this block is , where is the incidence vector of . Finally, implies that there are exactly blocks. □
Theorem 4. The following formulation is equivalent to the continuous multisource facility location problem:
Proof. Given a clustering, construct the matrices and as before and choose and . Such a choice has . Since vectors are pairwise orthogonal, we have that
Furthermore, , that is, is the center assigned to . Therefore, this construction gives a feasible solution with the same objective value, and the inequalities are tight at optimality.
Conversely, given any feasible matrices and of this formulation, Lemma 2 gives for the incidence vectors of a partition. Lemma 1 assures is of the form for some vectors . Again, will act as the center assigned to and constraints 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- 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 and the center matrices in the above three formulations play the same role as matrices and 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 -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 collect the conic constraints in (LR-D) involving , excluding . For , define the fixed-projector value:
The subproblem is conic for fixed and can be solved with any suitable conic optimization solver. It contains neither binary variables nor big- convexifications.
Since , the projector-space logic gives
is valid (recall 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 evaluations, the master problem reads
Notice that, just as with , we can exploit the facility-wise separability of 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 for the finite projector set and reconstruct 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- inequalities.
Algorithm 1 Outer Approximation for (LR-D)
Require: Initial , tolerance .
Set , , and .
repeat
Solve (17) at with a conic solver and obtain .
Add (18) and set .
Solve the master problem (LR-D-LB) globally; let be an optimal solution.
Set and .
until
return The best feasible projector and its associated clustering solution.
Every master value is a valid lower bound because all cuts underestimate , 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 is finite. Each iteration either closes the optimality gap or evaluates a new projector. Finite termination follows. □
For formulation (LR-SA), let
This finite set represents the feasible partitions without distinguishing their facility labels. For a fixed , define
For , write if , and zero otherwise. Thus, indicates whether and are in the same cluster. For an evaluated projector , define
This label-invariant quantity is zero if and at least one otherwise. Since , the corresponding logic cut is
It is exact at and otherwise is dominated by . In the discrete master, is a binary coassignment variable. After evaluating , the master reads
Note that if the fixed-projector subproblems and the master problems are solved exactly, Algorithm 1, with and replaced by and , 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 . This variant uses one rank- 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
The triangle inequality implies for every . Replacing by and relaxing idempotency gives the disaggregated relaxation
(SDP-RELAX-D)
Every feasible solution of (SDP-RELAX-D) yields an aggregate matrix . Dropping the requirement that admit this facility-wise decomposition gives the lighter relaxation
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 , one has whenever points and belong to the same cluster , and otherwise. In particular, states that the normalized association between two points cannot exceed the diagonal value of the cluster containing . The inequalities
provide a normalized transitivity condition. For example, if is associated with both and , then and 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 -variables, because 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
or the corresponding facility-wise constraints. A valid bound derived from a bounded region containing optimal centers is essential. Let and translate the demand points by . Translation does not change the distances or the optimal value. Let be any bounded region known to contain an optimal center for every possible nonempty cluster. It is enough to choose
Thus, the validity of the trace bound does not depend on a particular norm or on a particular construction of . 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 , the following bounds are valid:
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 denote a certified lower bound obtained from the selected model. When the SDP is stopped before optimality, must be taken from a dual-feasible solution rather than from the available primal objective. The lower bound requirement can be imposed in (PW-LB) and (LR-SA-LB). For (LR-D-LB), the corresponding inequality is . 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 and every facility location , the triangle inequality gives
Consequently, the pairwise master (PW-LB) can be strengthened with
This inequality is linear in the projector entries. Minimizing it over the doubly nonnegative relaxation of 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-LB) with epigraph variables can use the projection inequalities
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 is not assigned to one of facilities , then it is assigned to facility . In terms of the assignment variables, this implication is
Since every demand point is assigned to exactly one facility, the above set of constraints is equivalently written as for . In particular, it implies and prevents demand point from using a facility with label larger than .
For the projector-based formulations, . Therefore, the same conditions can be imposed directly on the projectors as
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 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
or, equivalently, . 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 single-facility problems
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 solve (SDP-RELAX-D), and define the fractional score matrix by . A nonempty partition is recovered from
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 is the dual bound obtained for a cluster , one may cache this value and add, for every facility label , the valid cut
The cut is active when facility contains all points of . 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 , as well as the complete instance for . We consider facilities in three different metric spaces, with . We compare the big- 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 . 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 we choose as (19) for . In this case, the convex hull of the demand points is contained in the corresponding Euclidean ball. For , we use . 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
where is the best feasible value and is the bound under comparison. For every method, 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 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 row are based on the same instances. All methods solve the instances in about two seconds on average. For , 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 , 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 , PW, LR-D, and LR-A each certify one run for , and no method certifies a run for . Formulation LR-A gives the smallest gap for , and PW for . At , 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 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 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.

Figure 1. Performance profiles over all matched instances and tested sizes.
| Time (s) MICO | PW | LR-D | LR-A | LR-SA | Opt. Gap (%) MICO | PW | LR-D | LR-A | LR-SA | Unsolved (%) MICO | PW | LR-D | LR-A | LR-SA | |||
| 10 | 1.1 | 0.9 | 2.0 | 1.9 | 1.4 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | |
| 2 | 0.4 | 0.6 | 1.2 | 1.1 | 1.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | |
| 3 | 1.2 | 0.8 | 2.0 | 1.8 | 1.4 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | |
| 20 | 1454.2 | 200.4 | 258.0 | 284.2 | 1094.5 | 8.5 | 0.0 | 0.0 | 0.0 | 0.2 | 40.0 | 0.0 | 0.0 | 0.0 | 0.0 | 13.3 | |
| 2 | 869.2 | 241.5 | 270.0 | 263.7 | 1201.5 | 2.5 | 0.0 | 0.0 | 0.0 | 0.1 | 13.3 | 0.0 | 0.0 | 0.0 | 0.0 | 6.7 | |
| 3 | 1436.7 | 242.7 | 269.8 | 245.5 | 1191.3 | 9.7 | 0.0 | 0.0 | 0.0 | 0.2 | 33.3 | 0.0 | 0.0 | 0.0 | 0.0 | 20.0 | |
| 30 | 2905.9 | 2745.2 | 2778.0 | 2775.1 | 3117.6 | 24.1 | 17.0 | 18.7 | 17.2 | 22.4 | 66.7 | 73.3 | 73.3 | 73.3 | 73.3 | ||
| 2 | 2581.4 | 2796.0 | 2830.7 | 2818.2 | 3228.0 | 23.5 | 19.0 | 18.9 | 20.4 | 22.5 | 66.7 | 73.3 | 73.3 | 73.3 | 86.7 | ||
| 3 | 2941.9 | 2818.1 | 2830.9 | 2846.7 | 3286.2 | 23.9 | 17.9 | 17.4 | 17.3 | 22.1 | 66.7 | 73.3 | 73.3 | 73.3 | 80.0 | ||
| 40 | 3600.0 | 3558.0 | 3553.1 | 3598.5 | 3600.0 | 34.8 | 23.1 | 23.0 | 22.9 | 26.6 | 100.0 | 93.3 | 93.3 | 93.3 | 100.0 | ||
| 2 | 3600.0 | 3600.0 | 3600.0 | 3600.0 | 3600.0 | 33.3 | 24.8 | 25.0 | 25.0 | 27.9 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | ||
| 3 | 3600.0 | 3600.0 | 3600.0 | 3600.0 | 3600.0 | 34.8 | 23.6 | 23.9 | 23.7 | 27.1 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | ||
| 50 | 3600.0 | 3600.0 | 3600.0 | 3600.0 | 3600.0 | 35.7 | 28.0 | 31.1 | 29.8 | 32.5 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | ||
| 2 | 3600.0 | 3600.0 | 3600.0 | 3600.0 | 3600.0 | 35.6 | 30.7 | 35.5 | 33.7 | 34.9 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | ||
| 3 | 3600.0 | 3600.0 | 3600.0 | 3600.0 | 3600.0 | 35.4 | 28.7 | 30.5 | 30.6 | 34.3 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 |
Table 1. Average runtime, final optimality gap, and percentage of unsolved instances. Boldfaced values indicate the best performance within each 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 . Their sharp decline at 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 and about 140 seconds for , against approximately 300 seconds for the facility-wise models when . Thus, the pairwise formulation combines effective cuts with cheaper SDP computations, consistently with its runtime and final-gap results.

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 and denote the average final optimality gaps, in percent, of MICO and projection method . The bars report in percentage points, so positive values favor the projection method.

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 , while the pairwise, disaggregated, and aggregated models are generally strongest for and . For , PW gives the largest improvement for all three values of .
Figure 4 compares the continuous-relaxation LB gap with MICO. If and denote their average gaps, the figure reports , 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 , while PW and LR-SA are strongest at . At , PW remains the strongest. Thus, projection information strengthens the initial lower bounds, although the best formulation depends on the instance size.

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- 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]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]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]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]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]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]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]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]Víctor Blanco, Justo Puerto, and Diego Ponce. Continuous location under the effect of ‘refraction’. Math. Program., 161:33–72, 2017.DOI
- [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]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]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]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
- [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.
- [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
- [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
- [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.
- [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
- [19]Leon Cooper. Location-allocation problems. Oper. Res., 11(3):331–343, 1963.DOI
- [20]Leon Cooper. Heuristic methods for location-allocation problems. SIAM Review, 6(1):37–53, 1964.DOI
- [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
- [22]Zvi Drezner and Jack Brimberg. Generating appropriate starting configurations for continuous multi-facility location models. IMA J. Manag. Math., 2026.DOI
- [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
- [25]Samuel Eilon, Carl D. T. Watson-Gandy, and Nicos Christofides. Distribution Management: Mathematical Modelling and Practical Analysis. Griffin, London, 1971.
- [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
- [27]Michel X Goemans. Semidefinite programming in combinatorial optimization. Math. Program., 79(1):143–161, 1997.DOI
- [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.
- [31]Robert E. Kuenne and Richard M. Soland. Exact and approximate solutions to the multisource Weber problem. Math. Program., 3:193–209, 1972.
- [33]Jean B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM J. Optim., 11(3):796–817, 2001.DOI
- [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.
- [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.
- [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.
- [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
- [38]Jiming Peng and Yu Wei. Approximating k-means-type clustering via semidefinite programming. SIAM J. Optim., 18(1):186–205, 2007.DOI
- [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
- [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
- [41]Kenneth E. Rosing. An optimal method for solving the (generalized) multi-Weber problem. Eur. J. Oper. Res., 58(3):414–426, 1992.DOI
- [42]Chuangchuang Sun and Ran Dai. Rank-constrained optimization and its applications. Automatica, 82:128–136, 2017. ISSN 0005-1098.DOI
- [43]Lieven Vandenberghe and Stephen Boyd. Semidefinite programming. SIAM Review, 38(1):49–95, 1996.
- [44]James E Ward and Richard E Wendell. Using block norms for location modeling. Oper. Res., 33(5):1074–1090, 1985.DOI
- [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