# The Ordered Median Tree Location Problem

Pozo Montaño, Miguel A.111Department of Statistics and Operational Research.
University of Seville. E-mail<EMAIL_ADDRESS>
Puerto Albandoz, Justo222Department of Statistics and Operational Research.
University of Seville. E-mail<EMAIL_ADDRESS>
Torrejón Valenzuela, Alberto333Institute of Mathematics of the University of
Seville. University of Seville. E-mail<EMAIL_ADDRESS>
###### Abstract

In this paper, we propose the Ordered Median Tree Location Problem (OMT). The
OMT is a single-allocation facility location problem where $p$ facilities must
be placed on a network connected by a non-directed tree. The objective is to
minimize the sum of the ordered weighted averaged allocation costs plus the
sum of the costs of connecting the facilities in the tree. We present
different MILP formulations for the OMT based on properties of the minimum
spanning tree problem and the ordered median optimization. Given that ordered
median hub location problems are rather difficult to solve we have improved
the OMT solution performance by introducing covering variables in a valid
reformulation plus developing two pre-processing phases to reduce the size of
this formulations. In addition, we propose a Benders decomposition algorithm
to approach the OMT. We establish an empirical comparison between these new
formulations and we also provide enhancements that together with a proper
formulation allow to solve medium size instances on general random graphs.

Keywords: Combinatorial Optimization, Discrete Location, Minimum Spanning
Tree, Ordered Median.

##  1 Introduction

Facility location problems are concerned with attaining the optimal placement
of facilities in order to minimize costs under certain considerations. In this
context, facilities connection is an important feature to include in these
problems. Gupta et al. (2001) introduced the Connected Facility Problem
(ConnFL), which aims to find the optimal location of a set of facilities that
require to be connected by a Steiner tree (see, e.g., Ljubić, 2021). Several
papers and surveys cover different aspects of the ConnFL and new cases of
study based on this problem (see, e.g, Fortz, 2015; Ljubić, 2021). As detailed
in Gollowitzer and Ljubić (2011), ConnFL is also related to other problems in
the literature, for example, rent-or-buy problems (Kumar et al., 2002),
Steiner tree-star problem (Lee et al., 1993; Khuller and Zhu, 2002), general
connected facility location problem (Bardossy and Raghavan, 2010), prize
collecting capacitated connected facility location problem (Leitner and Raidl,
2011) or the tree of hubs location problem (Contreras et al., 2010; Pozo et
al., 2021).

Although facilities connection can be modeled by using a Steiner tree problem,
there are several other possibilities to guarantee such connectivity. Another
common approach is exploiting the minimum spanning tree problem (MST)
structural properties, (see, e.g., Anazawa, 2001). The most relevant
properties of trees allow that the basic problem of finding a minimum cost
spanning tree can be solved efficiently in polynomial time (Kruskal, 1956;
Prim, 1957) and by means of linear programming tools (Miller et al., 1960;
Edmonds, 1970; Gavish, 1983; Martin, 1991 among several others). Optimization
problems related to spanning trees, or simply spanning tree problems, are
among the core problems in combinatorial optimization, see, e.g., the former
tree of hubs location problem (Contreras et al., 2010), the multi-objective
spanning tree problem (Hamacher and Ruhe, 1994) or the Stackelberg minimum
spanning tree problem (Cardinal et al., 2011). Moreover, spanning trees are
found in a wide range of applications (see, e.g., Clímaco and Pascoal, 2012).

To extend and provide a general framework for facility location problems, the
Discrete Ordered Median Location Problem (DOMP) was introduced (see Nickel and
Puerto, 2006; Boland et al., 2006), which could be used to model different
locations problems, as the $p$-median or the $p$-center problem. DOMP consists
in choosing $p$ facility locations and assigning each client to a facility
with the smallest allocation cost so to minimize a special objective function,
the so-called ordered median function. Given a vector of weights, this
function sorts these costs non-decreasingly and then performs the scalar
product with the given vector of weights. This adds a sorting feature to the
underlying location problem. The objective is to minimize the total allocation
cost after applying rank dependent compensation factors. Regarding the rank
dependent weights applied to the costs, its application intuitively arises
when these weights can be seen as compensation factors that try to diminish
unfair situations. DOMP objective function have been successfully applied in
the field of location analysis and distribution models (see, e.g., Puerto and
Tamir, 2005; Boland et al., 2006; Puerto, 2008; Marín et al., 2009; Kalcsics
et al., 2010a; Puerto and Rodríguez-Chía, 2015). DOMP structure has also been
embedded within other well-known problems giving rise to, e.g., ordered
weighted average problems (see Galand and Spanjaard, 2012; Fernández et al.,
2014, 2017) or ordered hub location problems (see Puerto et al., 2011, 2013,
2016; Pozo et al., 2021).

In this paper, we present the Ordered Median Tree Location Problem (OMT), a
single-allocation facility location problem where $p$ facilities must be
placed on a network connected by a non-directed tree. The objective is to
assign clients to its closest facility in order to minimize the ordered
allocation average cost plus the facilities tree connection average cost. In
our location problem, every client node can potentially become a facility and
these facilities are uncapacitated, i.e., can serve as many clients as needed.
Therefore, OMT has two main modeling aspects to model: the tree structure
defined by the network and the rank dependent compensation factors applied to
the costs of the system through the ordered median function. Section 2 extends
the problem description in more detail. Applications of the OMT can be given
for any general discrete facility location problem that require facilities to
be connected by a tree structure network (telecommunications or pipes as an
example). The order median component may model the need of compensate those
clients worst served (far from their closest facility).

OMT is a new problem that generalizes both MST and DOMP. OMT includes as a
particular case the MST when $p$ is considered equal to the number of client
nodes. If this is the case, clients would self-allocate to themselves giving
rise to a MST among all nodes. As the number of facilities $p$ decreases,
clients not required to be self-allocated start to appear, as it happens in
the ConnFL. Besides, if connectivity costs are set to zero, a “pure” DOMP
arises. For these reasons, OMT can be seen as a bi-objective model in which
the trade-off between connectivity and allocation costs requires to be
balanced. Moreover, by considering the DOMP objective function, we enrich the
possibilities in which client allocations are made, distinguishing OMT from
the ConnFL. In this paper, we analyze the median, $k$-center and $k$-trimmed
mean objectives, but the possibilities are many, e.g., we can model equity
criteria such as the range, sum of absolute differences or weighting inversely
proportional to the allocation costs, model obnoxious location problems (those
in which we want the facilities to be as far apart as possible), model
preferences with negative weight vectors, and more.

As aforementioned, solving the OMT implies solving a generalization of the
DOMP and the MST. For this reason, a Benders decomposition arises naturally as
a general OMT solving technique where the previous knowledge from DOMP and MST
is jointly exploited (see Martins de Sa et al., 2013 for a successful
application of Benders decomposition in a hub location problem with inner tree
structure). Benders decomposition (Benders, 1962) is a method for solving
mixed integer programming (MIP) problems that have special structure in the
constraint set, i.e., when fixing the complicating variables (integer
variables), the mathematical program reduces to an ordinary, easy to solve
linear problem. The technique relies on projection and problem separation,
followed by solution strategies of dualization, outer linearization and
relaxation (Lasdon, 2002; Minoux, 1986). In general terms, the complicating
variables of the original problem are projected out, resulting into an
equivalent model with fewer variables, but many more constraints. To achieve
optimality, a large number of these constraints will not be required,
suggesting then a strategy of relaxation that ignores all but a few of these
constraints. Over the years, different improvements have been proposed in
order to improve the performance of the Benders decomposition algorithm, (see
Geoffrion, 1972; Magnanti and Wong, 1981; Fischetti et al., 2010; Fortz and
Poss, 2009; Naoum-Sawaya and Elhedhli, 2013; Conforti and Wolsey, 2019;
Brandenberg and Stursberg, 2021). Several successful applications of Benders
decomposition to different problems rekindled the interest of the research
community for it, motivating the application to the OMT in the current work.
The reader could find a more detailed description about improvements in
Benders decomposition in the survey of Rahmaniani et al. (2017).

The contributions of this paper are the following. First, as it is shown in
Section 2.2 we present a new problem that was missing in the DOMP and
ConnFL/MST state-ot-the-art. Specifically, OMT generalizes two well-studied,
important problems in the sense that both facilities/clients connectivity and
clients allocations are jointly included. Therefore, this new problem arises
naturally as a bi-objective model in which we try to balance the trade-off
between connectivity and allocation costs. Second, we present different MILP
formulations for the OMT that arise naturally from the properties of the DOMP
and MST and we compare the number of variables and constraints as a function
of the number of ties in the cost matrix. Regarding to the MST subproblem, we
provide ad hoc OMT connectivity cuts and flow formulations. Third, we provide
theoretical results on the polytopes of the two main OMT formulations
including the number of variables and constraints as a function of the number
of ties in the cost matrix. This analysis can be extended to the DOMP and was
not previously given in the literature. Fourth, we present a different
alternative formulation that treats the OMT as a single tree over the complete
set of input nodes and we propose a Benders decomposition that arises
naturally as a general OMT solving technique where the previous knowledge from
DOMP and MST is jointly exploited. Fifth, we derive two new OMT fast
heuristics designed for providing initial solutions in the branching process
and we also take advantage of existing DOMP preprocessings for fixing
variables. Finally, we derive extensive computational results comparing in
detail the different formulations, enhancements and solution techniques
provided.

The remainder of the paper is organized as follows. In Section 2, we formally
define the OMT reviewing a scheme of some well-known related problems in the
literature. Section 3 presents the catalogue of formulations and algorithms
studied for the OMT. Section 4 shows the improvements made in order to enhance
the proposed models, initial solution computation and some preprocessing
phases developed for variable fixing. The empirical performance of the
resulting OMT formulations is analyzed in Section 5, where we present
extensive numerical results and a comparison of these formulations for
different particular cases. Finally, some conclusions are summarized in
Section 6.

##  2 Problem description

###  2.1 Notation and definition

In this section we formally introduce the OMT and fix the notation for the
rest of the paper. Let $G=(V,E)$ be a network where $V$ is the set of nodes
(assumed to be clients or potential facilities) and $E$ the set of edges
connecting nodes. In the OMT, $p\leq|V|$ facilities must be placed on nodes of
$V$ and connected by a non-directed tree. The model assumes single-allocation,
i.e., each client node has a unique facility where it is allocated. A weight
$c_{ij}\geq 0$ is defined for the cost of allocating client $i$ to facility
$j$ or as the design cost of edge $(i,j)$ whether both $i,j\in V$ are selected
facilities. According to many OMT related problems described in the
literature, these costs are assumed to be symmetrical between each pair of
nodes, $c_{ij}=c_{ji}$ for $i,j\in V$, and nodes can be allocated to
themselves with no cost, $c_{ii}=0$ for each $i\in V$, that is the so called
free self-service assumption. In addition, the allocation costs of the $|V|$
clients to their corresponding facilities are compensated using scaling factor
parameters $\lambda=(\lambda_{1},\ldots,\lambda_{|V|})$ (see Nickel and
Puerto, 2006; Boland et al., 2006; Kalcsics et al., 2010b; Marín et al., 2009,
2010; Puerto et al., 2011, 2013, 2016; Pozo et al., 2021 for different ordered
median location models). If client $i$ is allocated to facility $j$ at a cost
$c_{ij}$ and this cost is non-decreasingly ordered in the $\ell$-th position
among this type of costs, then this term would be scaled by $\lambda_{\ell}$,
i.e., the corresponding compensated cost would be $\lambda_{\ell}c_{ij}$.
Compensation of allocation costs is based on the fact that a solution that is
good for the system does not have to be acceptable for all single parties if
their costs to reach the system are too high in comparison to other parties.
We compensate this parties to prevent those sites from not using the system as
an act of fairness. For the sake of understandability, we summarize the
introduced notation in Table 1.

$G=(V,E)$ | undirected network where $V$ is the set of nodes and $E$ is the set of edges
---|---
$p$ | fixed number of facilities to locate
$c_{ij}$ | design cost of edge $(i,j)\in E$ or allocation cost between client $i$ and a facility
| placed at node $j$
$\ell\in V$ | index for the $\ell$-th position of the sorted allocation costs sequence
$\lambda_{\ell}$ | scaling factor for the $\ell$-th allocation cost
Table 1: Notation introduced for the OMT.

With the above notation, the OMT is to find the optimal location of $p$
facilities in a network in such a way that:

  1. 1.

Each client is allocated to exactly one facility.

  2. 2.

Facilities are connected together following a tree structure.

  3. 3.

Edge costs connecting facilities plus compensated ranked allocation costs are
minimized. Since the number of tree edges might be quite different from the
number of allocation arcs, the objective function will minimize the average
cost of the compensated ranked allocation costs plus the average cost of a
tree edge.

Observe that depending on the choices of the $\lambda$-vector we can obtain
different criteria to account for the costs in the objective function. For
instance, if $\lambda=(0,\ldots,0,1,\stackrel{{\scriptstyle k}}{{\ldots}},1)$
is considered, the allocation costs component of the objective function would
be the sum of the $k$-largest costs ($k$-centrum). This usually provides
different solutions or different allocation patterns for problems with
different $\lambda$, even though the optimal solution gets the same set of
facilities (see Puerto et al., 2011).

Figure 1 depicts different OMT solutions for a network example of $|V|=10$
clients (green circles) and cost matrix (1), where $p=5$ facilities (red
squares) are located. Considering rounded costs proportional to Euclidean
distances, client allocations to facilities (arrows) and the tree design
connecting facilities (dashed lines) are different according to different
criteria, namely (a) median $\lambda=(1,\stackrel{{\scriptstyle
10}}{{\ldots}},1)$, (b) $k$-centrum $\lambda=(0,\stackrel{{\scriptstyle
6}}{{\ldots}},0,1,\stackrel{{\scriptstyle 4}}{{\ldots}},1)$ and (c)
$k$-trimmed mean criterion $\lambda=(0,0,0,1,1,1,1,0,0,0)$. For the latter,
the three most expensive allocations, which correspond to nodes $8$, $9$ and
$10$, are ignored for the objective value computation. Due to this reason, for
this criterion, those clients could be allocated to any facility, despite in
Figure 1 appear allocated to its closest facility. We recall that OMT
objective function includes the minimization of $p$ edges costs plus a
variable number of allocation costs that will vary depending on the instance
size, the criteria selected, etc. That is, the contribution of the objective
function corresponding to the tree design part may change considerably
compared to the weight of the compensated ranked allocation costs. For that
reason, since the number of tree edges might be quite different from the
number of allocation arcs, the objective function minimizes the average cost
of the compensated ranked allocation costs plus the average cost of a tree
edge. Averaging the two features in the objective function is needed in order
to normalize the trade-off between these two elements. As a consequence of
this rationale, we have now a higher value in the $k$-centrum optimum because
we have the average between the higher costs divided by the number of costs
considered in the lambda vector (smaller denominator) instead of the total
average as in the median criterion.

A first consideration about the OMT is that it is an ${\cal NP}$-complete
problem, which comes from the hardness results of the different combinatorial
problems that give rise to the OMT (see Section 2.2). Both the $p$-median
location problem and the ordered median problem are known to be ${\cal
NP}$-complete problems on its decision version (Nickel and Puerto, 2006).

$\begin{pmatrix}\@add@centering\centering 0&25&10&18&28&21&32&35&40&47\\\
25&0&27&14&12&28&20&43&45&40\\\ 10&27&0&15&25&11&27&25&30&39\\\
18&14&15&0&10&14&14&29&32&32\\\ 28&12&25&10&0&21&7&34&34&28\\\
21&28&11&14&21&0&20&16&20&28\\\ 32&20&27&14&7&20&0&29&28&20\\\
35&43&25&29&34&16&29&0&7&25\\\ 40&45&30&32&34&20&28&7&0&20\\\
47&40&39&32&28&28&20&25&20&0\end{pmatrix}$ (1)

(a)

(b)

(c)

Figure 1: Three different OMT solutions according to (a) median [objective
value: 18.3], (b) $k$-centrum [objective value: 26.0] and (c) $k$-trimmed mean
criterion [objective value: 16.0], considering rounded costs proportional to
Euclidean distances.

###  2.2 Subproblems and related problems

As mentioned, the OMT has two main modeling aspects: the tree structure
defined by the facilities network (tree connectivity) and the rank-dependent
compensation factors applied to the operation cost of the system through the
ordered median function (sorting). Therefore, the OMT can be seen as the
classical $p$-Median Location Problem (PMED) adding two different features:
tree connectivity and sorting. In this way, the OMT has as subproblems
different well-known problems of the literature. The connectivity imposed to
PMED gives rise to the PMED with inner Connected Structure (PMEDC). When the
connected structure is a tree, we define the PMED with inner Tree Structure
(PMEDT), that is closely related to several known problems in the literature
as the tree-star network design problem (Nguyen and Knippel, 2007) or the
already mentioned connected facility location problem (Gollowitzer and Ljubić,
2011). The sorting feature can be included in PMED giving rise to the well-
known Discrete Ordered Median Location Problem (DOMP) (Nickel and Puerto,
2006). The union of both features gives raises to the DOMP with inner
Connected Structure (OMC) from which, when the connected structure considered
is a tree, we define our case of study, namely the OMT. The reader is referred
to Figure 2 for an overview of the different considered problems and their
relationships.

Figure 2: Diagram of relationships among the different OMT subproblems

In addition, the OMT can be understood as a subproblem of the Ordered Median
Tree of Hubs Location Problem (OMTHL) (Pozo et al., 2021), where flow exchange
between origin-destination pairs is considered for an OMT. The interested
reader may also check the tree of hubs location problem (Contreras et al.,
2010) and the ordered median hub location problem (Puerto et al., 2011).
Dealing with the OMT as a subproblem of the OMTHL is valuable in the sense
that the model structure is inherited. Nevertheless, the inherent complexity
of the OMTHL and the fact that the OMT holds its own interest, suggests that
the OMT should be studied as a singular problem.

##  3 Analyzing the OMT: formulations, polyhedral descriptions and Benders
decomposition

###  3.1 Two OMT formulations

In the following we will present a general integer programming formulation for
the OMT. Given the set of edges $E=\\{(i,j)\ |\ i,j\in V,i<j\\}$, we define
the set of arcs $A=\\{(i,j),(j,i)\ |\ (i,j)\in E\\}\cup\\{(i,i)\ |\ i\in
V\\}$, where loops connecting a node to itself are allowed. For modeling
purposes the following variables are defined:

  * •

$x_{ij}\in\\{0,1\\}$ for $(i,j)\in A$, equal to 1 if client $i$ is allocated
to facility $j$, 0 otherwise.

  * •

$z_{ij}\in\\{0,1\\}$ for $(i,j)\in E$, equal to 1 if an edge $(i,j)$ connects
facilities $i,j\in V$, 0 otherwise.

  * •

$x_{ij}^{\ell}\in\\{0,1\\}$ for $(i,j)\in A,\ell\in V$, equal to 1 if client
$i$ is allocated to facility $j$ and $c_{ij}$ is ranked in the $\ell$-th
position, 0 otherwise.

Along the text, we would assume working with complete networks. However, the
proposed formulations are valid for general graphs with edge set $E$ and arc
set $A$, as long as the connectivity of the network is ensured. The
formulation presented below is based on the DOMP three-index formulation first
introduced by Boland et al., 2006, including the tree connectivity feature of
the OMT. Therefore, the formulation can be defined as follows:

$\displaystyle\hskip
28.45274ptF1_{x^{\ell}}^{\mathcal{T}}:\min\quad\frac{1}{\displaystyle{\sum_{\ell\in
V}\lambda_{\ell}}}\sum_{\ell\in V}\sum_{(i,j)\in
A}\lambda_{\ell}c_{ij}x_{ij}^{\ell}+\frac{1}{p-1}\sum_{(i,j)\in
E}c_{ij}z_{ij}$ (2a) $\displaystyle\textrm{s.t.:}\hskip 7.11317pt\sum_{i\in
V}x_{ii}=p$ (2b) $\displaystyle\hskip 34.99677pt\sum_{j\in V}x_{ij}=1$
$\displaystyle i\in V$ (2c) $\displaystyle\hskip 34.99677ptx_{ij}\leq x_{jj}$
$\displaystyle(i,j)\in A:i\neq j$ (2d) $\displaystyle\hskip
34.99677pt2z_{ij}\leq x_{ii}+x_{jj}$ $\displaystyle(i,j)\in E$ (2e)
$\displaystyle\hskip 34.99677ptz_{ij}\in\mathcal{T}$ $\displaystyle(i,j)\in E$
(2f) $\displaystyle\hskip 34.99677pt\sum_{\ell\in V}x_{ij}^{\ell}=x_{ij}$
$\displaystyle(i,j)\in A$ (2g) $\displaystyle\hskip 34.99677pt\sum_{(i,j)\in
A}x_{ij}^{\ell}=1$ $\displaystyle\ell\in V$ (2h) $\displaystyle\hskip
34.99677pt\sum_{(i,j)\in A}c_{ij}x_{ij}^{\ell}\leq\sum_{(i,j)\in
A}c_{ij}x_{ij}^{\ell+1}$ $\displaystyle\ell\in V:\ell<|V|$ (2i)
$\displaystyle\hskip 34.99677ptx_{ij}\in\\{0,1\\}$ $\displaystyle(i,j)\in A$
(2j) $\displaystyle\hskip 34.99677ptx_{ij}^{\ell}\in\\{0,1\\}$
$\displaystyle(i,j)\in A,\ell\in V$ (2k) $\displaystyle\hskip
34.99677ptz_{ij}\in\\{0,1\\}$ $\displaystyle(i,j)\in E.$ (2l)

The objective function (2a) minimizes the compensated allocation costs
weighted by the number of allocations considered (first component) plus the
design cost of the tree connecting facilities weighted by the number of edges
(second component). In other words, (2a) minimizes the average cost of an
allocation plus the average cost of a tree edge. The group of constraints
(2b), (2c) and (2d) models the allocation of clients to facilities.
Specifically, constraint (2b) fixes the number of facilities in the network to
$p$, constraints (2c) ensure that each client is allocated to exactly one
facility and constraints (2d) ensure that no client is allocated to a non-
facility node. Constraints (2e) relate the allocation variables to the design
variables, imposing that each edge of the facilities spanning tree can only be
selected if both edge nodes are facilities. Note that these constraints are
obtained from the unification of two simpler group of constraints ($z_{ij}\leq
x_{ii}\ \&\ z_{ij}\leq x_{jj}$ for $(i,j)\in E$). Constraints (2f) model the
connectivity feature of the OMT describing the facilities spanning tree
polytope $\mathcal{T}$. These constraints are different depending on the tree
characterization considered (see Section 3.3). Finally, constraints (2g), (2h)
and (2i) model the sorting feature of the problem. Specifically, constraints
(2g) relate the sorting variables to the allocation variables guaranteeing
that if the allocation of client $i$ to facility $j$ is selected, then only
one sorting position can be assumed by this allocation, constraints (2h)
ensures that every sorting position must be occupied and constraints (2i) sort
allocation costs in non-decreasing order.

Note that, since $x_{ij}=\sum_{\ell\in V}x_{ij}^{\ell}$, by constraint (2g) it
is possible to relax the integrality constraint (2j), defining
$x_{ij}\in[0,1]$ for all $(i,j)\in A$. Furthermore, each $x_{ij}$ can be
replaced by a sum $\sum_{\ell\in V}x_{ij}^{\ell}$ unifying the allocation and
sorting set of variables. For the last, despite the number of variables is
reasonably reduced, the number of constraints increases and preliminary tests
have shown us that such unification is not efficient in computational terms.
For this reason disaggregated formulations are presented along the text.

Let us now consider the ordered sequence of unique allocation costs of
$c_{ij}\geq 0$ for $i,j\in V$:

$c_{(0)}:=0<c_{(1)}<c_{(2)}<\ldots<c_{(|H|)}=\max_{i,j\in V}c_{ij},$

where $|H|$ is the number of different non-zero elements of the above
allocation cost sequence and $H=\\{1,\ldots,|H|\\}$. This ordering can be used
to perform the sorting process of the allocation costs. Let us define the
following variables (namely covering variables in the following):

  * •

$u_{\ell h}\in\\{0,1\\}$ for $\ell\in V,h\in H$ if the $\ell$-th allocation
cost is at least $c_{(h)}$,

that is, the $\ell$-th smallest cost is equal to $c_{(h)}$ if and only if
$u_{\ell 1}=...=u_{\ell h}=1$ and $u_{\ell h+1}=...=u_{\ell|H|}=0$.

######  Example 3.1.

Given $c=\begin{pmatrix}0&2&4\\\ 2&0&0\\\ 4&0&0\end{pmatrix}$, $p=1$ and
$\lambda=(1,1,1)$ an OMT solution implies $x_{12}^{3}=x_{22}^{1}=x_{32}^{2}=1$
(or equivalently $x_{12}^{3}=x_{22}^{2}=x_{32}^{1}=1$). Since
$c_{(0)}:=0<c_{(1)}=2<c_{(2)}=4$, we have $u=\begin{pmatrix}0&0\\\ 0&0\\\
1&0\end{pmatrix}$.

As reviewed in previous works (see Puerto et al., 2011, Puerto et al., 2013
and Pozo et al., 2021 among others) sorting costs can be rather difficult in
large instances when using the $x^{\ell}$ variables previously defined.
Besides, formulations using covering variables (see Elloumi et al., 2004;
Nickel and Puerto, 2006; Puerto, 2008; Espejo et al., 2009; Marín et al.,
2009, 2010; Puerto et al., 2011; García et al., 2011) can be used to downsize
the number of variables in use.

Recalling the general scheme proposed in the previous section, we can rewrite
$F1_{x^{\ell}}^{\mathcal{T}}$ as follows:

$\displaystyle\hskip
28.45274ptF1^{\mathcal{T}}_{u}:\min\quad\frac{1}{\displaystyle{\sum_{\ell\in
V}}\lambda_{\ell}}\sum_{\ell\in V}\sum_{h\in H}\lambda_{\ell}u_{\ell
h}(c_{(h)}-c_{(h-1)})+\frac{1}{p-1}\sum_{(i,j)\in E}c_{ij}z_{ij}$ (3a)
$\displaystyle\textrm{s.t.:}\hskip 7.11317pt\sum_{i\in V}x_{ii}=p$ (3b)
$\displaystyle\hskip 34.99677pt\sum_{j\in V}x_{ij}=1$ $\displaystyle i\in V$
(3c) $\displaystyle\hskip 34.99677ptx_{ij}\leq x_{jj}$ $\displaystyle(i,j)\in
A:i\neq j$ (3d) $\displaystyle\hskip 34.99677pt2z_{ij}\leq x_{ii}+x_{jj}$
$\displaystyle(i,j)\in E$ (3e) $\displaystyle\hskip
34.99677ptz_{ij}\in\mathcal{T}$ $\displaystyle(i,j)\in E$ (3f)
$\displaystyle\hskip 34.99677pt\sum_{\ell\in V}u_{\ell h}=\sum_{i,j\in
V:c_{ij}\geq c_{(h)}}x_{ij}$ $\displaystyle h\in H$ (3g) $\displaystyle\hskip
34.99677ptu_{\ell h}\leq u_{\ell+1h}$ $\displaystyle h\in H,\ell\in
V:\ell<|V|$ (3h) $\displaystyle\hskip 34.99677ptu_{\ell h}\geq u_{\ell h+1}$
$\displaystyle h\in H,\ell\in V:h<|H|$ (3i) $\displaystyle\hskip
34.99677ptx_{ij}\in\\{0,1\\}$ $\displaystyle(i,j)\in A$ (3j)
$\displaystyle\hskip 34.99677ptu_{\ell h}\in\\{0,1\\}$ $\displaystyle h\in
H,\ell\in V$ (3k) $\displaystyle\hskip 34.99677ptz_{ij}\in\\{0,1\\}$
$\displaystyle(i,j)\in E.$ (3l)

Constraints (3g) state that the number of allocations with a cost at least
$c_{(h)}$ must be equal to the number of sites that support allocation costs
greater than or equal to $c_{(h)}$ and constraints (3h) and (3i) sorts the
values of the sorting variables $u$ in non-decreasing order. As indicated in
Labbé et al., 2017 and Marín et al., 2009, the extra sorting group of
constraints (3i) is redundant, nevertheless, they are binding for some of the
results on Section 3.2 and have been proved to strengthen the covering
formulation.

Note that $F1^{\mathcal{T}}_{u}$ is defined over a set $H$ whose cardinality
depends on the unique non-zero elements in the cost matrix. We recall that OMT
assumes free self-service and symmetrical costs, what implies a significant
number of repetitions in the cost matrix and a diagonal of zeros. Te be more
precise, let $\hat{\alpha}$ be the number of ties within the part of the cost
matrix above the diagonal and by $\hat{\chi_{0}}$ a binary parameter equal to
1 if there is at least a 0 within the part of the cost matrix, zero otherwise.
Thus,

  * •

$0\leq\hat{\alpha}\leq\frac{1}{2}(|V|^{2}-|V|)-1$.

  * •

$\hat{\alpha}=\frac{1}{2}(|V|^{2}-|V|)-\hat{\chi_{0}}-|H|$.

Note that $\hat{\alpha}$ can also be easily computed as
$\hat{\alpha}=\sum_{i=0}^{|H|}(m_{i}-1)$, where $m_{i}$ stands for the
multiplicity of cost $c_{(h)}$ within the part of the cost matrix above the
diagonal.

We provide in Table 2 theoretical size values in terms of variables
($\\#variables$) and constraints ($\\#constraints$) of
$F1_{x^{\ell}}^{\mathcal{T}}$ and $F1^{\mathcal{T}}_{u}$ OMT formulations.
Note that, the dimensions do not include the redundant set (3i) for
$F1^{\mathcal{T}}_{u}$, and both formulations are specified independently of
the $\mathcal{T}$ used but including (2f) and (3f) as constraints.

| $\\#variables$ | $\\#constrains$
---|---|---
$F1_{x^{\ell}}^{\mathcal{T}}$: | $|V|^{3}+\frac{3|V|^{2}}{2}-\frac{|V|}{2}$ | $3|V|^{2}+|V|$
$F1^{\mathcal{T}}_{u}$: | $|V||H|+\frac{3|V|^{2}}{2}-\frac{|V|}{2}=$ | $2|V|^{2}+|H||V|-|V|+1=$
| $\frac{1}{2}|V|^{3}+|V|^{2}-(\hat{\chi_{0}}+\hat{\alpha}+\frac{1}{2})|V|$ | $\frac{1}{2}|V|^{3}+\frac{3}{2}|V|^{2}-(\hat{\chi_{0}}+\hat{\alpha}+1)|V|+1$
Table 2: Theoretical model dimensions in the OMT formulations

We observe from Table 2 the following property:

######  Property 3.1.

  * (a)

$F1^{\mathcal{T}}_{u}$ has
$\frac{1}{2}|V|^{3}+\frac{1}{2}|V|^{2}+(\hat{\chi_{0}}+\hat{\alpha})|V|>0$
less variables than $F1_{x^{\ell}}^{\mathcal{T}}$.

  * (b)

The difference of constraints between $F1^{\mathcal{T}}_{u}$ and
$F1_{x^{\ell}}^{\mathcal{T}}$ is
$\frac{1}{2}|V|^{3}-\frac{3}{2}|V|^{2}-(\hat{\chi_{0}}+\hat{\alpha}+2)|V|+1$.
Therefore, $F1^{\mathcal{T}}_{u}$ has less constraints than
$F1_{x^{\ell}}^{\mathcal{T}}$ if and only if

$\hat{\alpha}\geq\frac{1}{2}|V|^{2}-\frac{3}{2}|V|-\hat{\chi_{0}}-1,$

that is, $|H|\leq|V|+1$.

###### Proof.

(a) Is straightforward to prove.

(b) In terms of constraints, the difference between
$F1_{x^{\ell}}^{\mathcal{T}}$ and $F1^{\mathcal{T}}_{u}$ is the sorting group
of constraints, (2g)-(2i) and (3g)-(3h) respectively. For this group, there
exists a total of $|V|^{2}+2|V|-1$ constraints in
$F1_{x^{\ell}}^{\mathcal{T}}$ and
$|H||V|=\frac{1}{2}|V|^{3}-\frac{1}{2}|V|^{2}-(\hat{\chi_{0}}+\hat{\alpha})|V|$
constraints in $F1^{\mathcal{T}}_{u}$. Therefore, subtracting both expressions
we get that the difference in the number of constraints is
$\frac{1}{2}|V|^{3}-\frac{3}{2}|V|^{2}-(\hat{\chi_{0}}+\hat{\alpha}+2)|V|+1$,
that is negative only if we have
$\hat{\alpha}>\frac{1}{2}|V|^{2}-\frac{3}{2}|V|-\hat{\chi_{0}}-2+\frac{1}{|V|}$
(that is $\hat{\alpha}\geq\frac{1}{2}|V|^{2}-\frac{3}{2}|V|-\hat{\chi_{0}}-1$)
and $|H|<|V|+2-\frac{1}{|V|}$ (that is $|H|\leq|V|+1$).

∎

Formulation of the ordered median using variables $x^{\ell}$ is the general
representation used to describe the problem, while formulation using covering
variables $u$ performs best computationally. There exist several more
formulations to represent the ordered median problem (see, e.g., Labbé et al.,
2017). However, the analysis of such other formulations embedded within the
OMT structure is beyond the scope of this paper.

###  3.2 Theoretical results on polytopes

In this section, we provide a theoretical comparison of the polytopes
regarding our formulations $F1^{\mathcal{T}}_{x^{\ell}}$ and
$F1^{\mathcal{T}}_{u}$ presented in previous Section 3. Comparing OMT
formulations is equivalent to comparing DOMP formulations because both
problems only differ in the connection feature, which is modeled by the same
group of constraints for every formulation (see Section 3.3 for more details).
Therefore, some of the results we adapt to our OMT polytopes comparison are
presented in Labbé et al. (2017). Nevertheless, our goal is to state the
formal relationships between the linear relaxations of the considered
formulations and study the similarities between these polytopes describing in
detail the degenerate case of no ties in the cost matrix. Also, note that in
this section the OMT assumptions have been relaxed in an attempt to generalize
these results.

####  3.2.1 Analyzing polytopes with a general cost matrix

The results presented in this subsection are valid for a general cost matrix
independently of the number of ties. The reader may note that OMT does not
really require free self-service and symmetric cost assumptions. Without these
two assumptions our formulation is still valid although it slightly changes
the meaning of costs $c_{ii}$ that would turn to be the opening cost of
facility $i$ plus de allocation cost of client $i$ to facility $i$ (if a
facility is opened $i$, client $i$ has to be allocated to such facility). Let
$\Omega_{x^{\ell}}^{\mathcal{T}}$ be the set of points satisfying constraints
(2b)-(2k) and $\Omega_{u}^{\mathcal{T}}$ be the set of points satisfying
constraints (3b)-(3k). Let also $\phi_{x^{\ell}}(\cdot)$ and $\phi_{u}(\cdot)$
denote the value of the objective functions, (2a) and (3a) respectively,
evaluated at a feasible point $(\cdot)$ and
$P(\Omega_{\mathcal{S}}^{\mathcal{T}})$ for $\mathcal{S}\in\\{x^{\ell},u\\}$
the polytope defined from the linear relaxation of
$\Omega_{\mathcal{S}}^{\mathcal{T}}$. For the sake of understandability, we
remove the tree notation $\mathcal{T}$ in this section which is not relevant.
A first property to recall is the following.

######  Property 3.2.

There exist two mappings $f$ and $g$,

$\displaystyle
f:\mathbb{R}^{|V|^{2}}\times\mathbb{R}^{|V|^{2}}\times\mathbb{R}$
$\displaystyle\longmapsto\mathbb{R}^{|V|^{2}}\times\mathbb{R}^{|V|^{2}}\times\mathbb{R}^{|V||H|},$
$\displaystyle(x_{ij},z_{ij},x_{ij}^{\ell})$
$\displaystyle\longmapsto(x_{ij},z_{ij},u_{\ell h}).$ $\displaystyle
g:\mathbb{R}^{|V|^{2}}\times\mathbb{R}^{|V|^{2}}\times\mathbb{R}^{|V||H|}$
$\displaystyle\longmapsto\mathbb{R}^{|V|^{2}}\times\mathbb{R}^{|V|^{2}}\times\mathbb{R}^{|V|^{3}},$
$\displaystyle(x_{ij},z_{ij},u_{\ell h})$
$\displaystyle\longmapsto(x_{ij},z_{ij},x_{ij}^{\ell}).$

such that,

  * •

For any point $(x_{ij},z_{ij},x_{ij}^{\ell})\in P(\Omega_{x^{\ell}})$, then
$\phi_{x^{\ell}}(x_{ij},z_{ij},x_{ij}^{\ell})=\phi_{u}(f(x_{ij},z_{ij},x_{ij}^{\ell}))$.

  * •

For any point $(x_{ij},z_{ij},u_{\ell h})\in P(\Omega_{u})$, then
$\phi_{u}(x_{ij},z_{ij},u_{\ell h})=\phi_{x^{\ell}}(g(x_{ij},z_{ij},u_{\ell
h}))$.

These mapping definitions are given in Labbé et al. (2017). Via these
mappings, several polytope comparisons can be attained.

######  Property 3.3.

  1. (a)

$g(P(\Omega_{u}))\subset P(\Omega_{x^{\ell}})$.

  2. (b)

$f(P(\Omega_{x^{\ell}}))\not\subset P(\Omega_{u})$.

###### Proof.

  1. (a)

See Theorem 1 in Labbé et al. (2017).

  2. (b)

Consider the network example depicted in Figure 3, where client nodes
(circles) allocate to a single facility (square).

096543218123 Figure 3: Network example.

Let the following feasible solution (non-optimal) defined by the values:

$\displaystyle x_{11}$ $\displaystyle=1,$ $\displaystyle x_{12}$
$\displaystyle=0,$ $\displaystyle x_{13}$ $\displaystyle=0,$ $\displaystyle
x_{21}$ $\displaystyle=1,$ $\displaystyle x_{22}$ $\displaystyle=0,$
$\displaystyle x_{23}$ $\displaystyle=0,$ $\displaystyle x_{31}$
$\displaystyle=1,$ $\displaystyle x_{32}$ $\displaystyle=0,$ $\displaystyle
x_{33}$ $\displaystyle=0,$

$\displaystyle z_{12}$ $\displaystyle=0,$ $\displaystyle z_{13}$
$\displaystyle=0,$ $\displaystyle z_{23}$ $\displaystyle=0,$

$\displaystyle x^{1}_{11}$ $\displaystyle=0.9,$ $\displaystyle x^{2}_{11}$
$\displaystyle=0,$ $\displaystyle x^{3}_{11}$ $\displaystyle=0.1,$
$\displaystyle x^{1}_{21}$ $\displaystyle=0,$ $\displaystyle x^{2}_{21}$
$\displaystyle=1,$ $\displaystyle x^{3}_{21}$ $\displaystyle=0,$
$\displaystyle x^{1}_{31}$ $\displaystyle=0.1,$ $\displaystyle x^{2}_{31}$
$\displaystyle=0,$ $\displaystyle x^{3}_{31}$ $\displaystyle=0.9,$

$x^{\ell}_{ij}=0\ \text{otherwise}.$

We can verify that the previous solution satisfies the group of constraints
defining $P(\Omega_{x^{\ell}})$ (shown only for sorting constraints):

     * •

$\sum_{\ell\in V}x_{ij}^{\ell}=x_{ij},\quad(i,j)\in A.$

$\displaystyle x^{1}_{11}+x^{2}_{11}+x^{3}_{11}$ $\displaystyle=1=x_{11},$
$\displaystyle x^{1}_{21}+x^{2}_{21}+x^{3}_{21}$ $\displaystyle=1=x_{21},$
$\displaystyle x^{1}_{31}+x^{2}_{31}+x^{3}_{31}$ $\displaystyle=1=x_{31},$
Otherwise trivially equal to 0.

     * •

$\sum_{(i,j)\in A}x_{ij}^{\ell}=1,\quad\ell\in V.$

$\displaystyle x^{1}_{11}+x^{1}_{21}+x^{1}_{31}+0\ldots$ $\displaystyle=1$
$\displaystyle x^{2}_{11}+x^{2}_{21}+x^{2}_{31}+0\ldots$ $\displaystyle=1$
$\displaystyle x^{3}_{11}+x^{3}_{21}+x^{3}_{31}+0\ldots$ $\displaystyle=1$

     * •

$\sum_{(i,j)\in A}c_{ij}x_{ij}^{\ell}\leq\sum_{(i,j)\in
A}c_{ij}x_{ij}^{\ell+1},\quad\ell\in V:\ell<|V.$

$\displaystyle c_{11}x^{1}_{11}+c_{31}x^{1}_{31}+0\ldots=0.9\cdot 0+0.1\cdot
9=0.9\leq c_{21}x^{2}_{21}+0\ldots=1\cdot 3=3$ $\displaystyle
c_{21}x^{2}_{21}+0\ldots=1\cdot 3=3\leq
c_{11}x^{3}_{11}+c_{31}x^{3}_{31}+0\ldots=0.9\cdot 9+0.1\cdot 0=8.1$

We can give an expression for $u$ variables using $f$ definition, which is
given by the system of equations:

$\displaystyle f:(x_{ij},z_{ij},x_{ij}^{\ell})$
$\displaystyle\longmapsto(x_{ij},z_{ij},u_{\ell h}),$ $\displaystyle u_{\ell
h}$ $\displaystyle=\sum_{i,j\in V:c_{ij}\geq c_{(h)}}x^{\ell}_{ij}\quad\forall
h\in H,\ell\in V.$ (4)

Therefore,

$\displaystyle u_{11}=0.1,$ $\displaystyle\cdots$ $\displaystyle\cdots$
$\displaystyle\cdots$ $\displaystyle\cdots$ $\displaystyle u_{18}=0.1,$
$\displaystyle u_{21}=1$ $\displaystyle\cdots$ $\displaystyle u_{23}=1,$
$\displaystyle u_{24}=0,$ $\displaystyle\cdots$ $\displaystyle u_{28}=0,$
$\displaystyle u_{31}=0.9,$ $\displaystyle\cdots$ $\displaystyle\cdots$
$\displaystyle\cdots$ $\displaystyle\cdots$ $\displaystyle u_{38}=0.9,$

which does not satisfy constraints $u_{\ell h}\leq u_{\ell+1h}$ for $h\in
H,\ell\in V:\ell<|V|$ in the relaxed polytope $P(\Omega_{u})$.

∎

As a consequence, we have found a feasible solution in $P(\Omega_{x^{\ell}})$
whose image by $f$ is not feasible in $P(\Omega_{u})$. Next, we study the
objective function value of the points $(x_{ij},z_{ij},x^{\ell}_{ij})\in
P(\Omega_{x^{\ell}})$ such that $f(x_{ij},z_{ij},x^{\ell}_{ij})\notin
P(\Omega_{u})$. First, let us consider the following polytope namely
$P(\Omega^{\prime}_{x^{\ell}})$, where constraints (2i) are replaced by
constraints

$\sum_{i,j\in V:c_{ij}\geq c_{(h)}}x^{\ell}_{ij}+\sum_{i,j\in
V:c_{ij}<c_{(h)}}x^{\ell+1}_{ij}\leq 1,\quad h\in H,\ell\in V:\ell<|V|,$ (5)

which are a consequence of the staircase inequalities in Labbé et al. (2017).
Observe that,

######  Property 3.4.

  1. (a)

$f(P(\Omega^{\prime}_{x^{\ell}}))=P(\Omega_{u})$.

  2. (b)

$g(P(\Omega_{u}))\subset P(\Omega^{\prime}_{x^{\ell}})$.

###### Proof.

  1. (a)

Following the results in Labbé et al. (2017), $g$ satisfies the equality of
$f$ by construction, thus $f(g(u))=u$. This implies
$f(P(\Omega^{\prime}_{x^{\ell}}))\supset P(\Omega_{u})$ and we only need to
prove then $f(P(\Omega^{\prime}_{x^{\ell}}))\subset P(\Omega_{u})$. Given
$(x_{ij},z_{ij},x^{\ell}_{ij})\in P(\Omega^{\prime}_{x^{\ell}})$ we prove that
$f(x_{ij},z_{ij},x^{\ell}_{ij})$ satisfies constraints (3g)-(3i). Constraints
(3i) are satisfied by means of $f$ definition,

$u_{\ell h}=\sum_{i,j\in V:c_{ij}\geq c_{(h)}}x_{ij}^{\ell}\geq\sum_{i,j\in
V:c_{ij}\geq c_{(h+1)}}x_{ij}^{\ell}=u_{\ell h+1},$

constraints (3g) are satisfied because of the following

$\sum_{\ell\in V}u_{\ell h}=\sum_{\ell\in V}\sum_{i,j\in V:c_{ij}\geq
c_{(h)}}x_{ij}^{\ell}=\sum_{i,j\in V:c_{ij}\geq c_{(h)}}\sum_{\ell\in
V}x_{ij}^{\ell}\stackrel{{\scriptstyle(\ref{OMT_f1_c6})}}{{=}}\sum_{i,j\in
V:c_{ij}\geq c_{(h)}}x_{ij},$

and constraints (3h) because

$\displaystyle u_{\ell h}$ $\displaystyle=\sum_{i,j\in V:c_{ij}\geq
c_{(h)}}x_{ij}^{\ell}\stackrel{{\scriptstyle(\ref{21consequence})}}{{\leq}}1-\sum_{i,j\in
V:c_{ij}<c_{(h)}}x_{ij}^{\ell+1}\stackrel{{\scriptstyle(\ref{OMT_f1_c7})}}{{=}}\sum_{(i,j)\in
A}x_{ij}^{\ell+1}-\sum_{i,j\in V:c_{ij}<c_{(h)}}x_{ij}^{\ell+1}=$
$\displaystyle=\sum_{i,j\in V:c_{ij}<c_{(h)}}x_{ij}^{\ell+1}+\sum_{i,j\in
V:c_{ij}\geq c_{(h)}}x_{ij}^{\ell+1}-\sum_{i,j\in
V:c_{ij}<c_{(h)}}x_{ij}^{\ell+1}=\sum_{i,j\in V:c_{ij}\geq
c_{(h)}}x_{ij}^{\ell+1}=u_{\ell+1,h}.$

  2. (b)

By Property 3.3, we know $g(P(\Omega_{u}))\subset P(\Omega_{x^{\ell}})$.
Hence, we just need to prove that constraints (5) are satisfied. By
constraints (3h) we get

$\displaystyle u_{\ell h}\leq u_{\ell+1h}$ $\displaystyle\implies\sum_{i,j\in
V:c_{ij}\geq c_{(h)}}x_{ij}^{\ell}\leq\sum_{i,j\in V:c_{ij}\geq
c_{(h)}}x_{ij}^{\ell+1}\implies\sum_{i,j\in
V:c_{ij}<c_{(h)}}x_{ij}^{\ell+1}+\sum_{i,j\in V:c_{ij}\geq
c_{(h)}}x_{ij}^{\ell}\leq 1.$

∎

Consequently, the following result can be given as a conclusion.

######  Property 3.5.

$\phi_{u}=\phi^{\prime}_{x^{\ell}}\geq\phi_{x^{\ell}}.$

###### Proof.

This property is a consequence of Property 3.2 and
$P(\Omega_{u})=f(P(\Omega^{\prime}_{x^{\ell}}))\subset
f(P(\Omega_{x^{\ell}}))$. ∎

As an observation to Property 3.5, our computational experience shows the
equality $\phi_{u}=\phi^{\prime}_{x^{\ell}}=\phi_{x^{\ell}}$ holds in the
optimum.

####  3.2.2 Analyzing polytopes with no ties in the cost matrix

We analyze next the particular case when no ties exists in the cost matrix. We
observe that in such case, the previous definition of $f$ holds while $g$ (see
Labbé et al., 2017) transforms into a much simpler expression:

$\displaystyle
g:\mathbb{R}^{|V|^{2}}\times\mathbb{R}^{|V|^{2}}\times\mathbb{R}^{|V|^{3}}$
$\displaystyle\longmapsto\mathbb{R}^{|V|^{2}}\times\mathbb{R}^{|V|^{2}}\times\mathbb{R}^{|V|^{3}},$
$\displaystyle(x_{ij},z_{ij},u_{\ell h})$
$\displaystyle\longmapsto(x_{ij},z_{ij},x_{ij}^{\ell}),$
$\displaystyle\medmath{x_{ij}^{\ell}}$
$\displaystyle=\medmath{\left\\{\begin{array}[]{ll}0&\text{ if
}\ell<\ell(h)\text{ or }x_{ij}=0,\\\
\min\left\\{x_{ij}-\sum_{k<\ell}x_{ij}^{k},u_{\ell
h}-u_{\ell,h+1}\right\\}&\text{ if }\ell\geq\ell(h),\end{array}\right.}$ (8)

where $\ell(h)=\min\left\\{\ell:u_{\ell h}-u_{\ell,h+1}>0\right\\}$ for
$h=1,\ldots,H$ and $u_{\ell,H+1}=u_{\ell H}$. We assume that if $u_{\ell
h}-u_{\ell,h+1}=0$ for all $\ell\in V$ then $\ell(h)=+\infty$.

Furthermore, when there are no ties in the cost matrix, we can give an
expression for $f^{-1}$ using equations in (4). Because no ties exist in the
cost matrix, we have that each $c_{(h)}$ is uniquely related to a $c_{ij}$,
that is, there exists a bijective mapping $\beta$ between the sequence of
costs defined as

$\displaystyle\beta:H$ $\displaystyle\longmapsto\\{ij\ |\ i,j\in V\\},$
$\displaystyle c_{(h)}$ $\displaystyle\longmapsto
c_{\beta(h)}=c_{i_{h}j_{h}}.$

For every $\ell\in V$, system (4) can be expressed in matrix form as follows.
Let $\underline{\textbf{u}}_{\ell}=(u_{\ell
1},\ldots,u_{\ell|V|^{2}})^{{}^{\prime}}$ and
$\underline{\textbf{x}}^{\ell}=(x^{\ell}_{11},\ldots,x^{\ell}_{1|V|},\ldots,x^{\ell}_{|V|1},\ldots,x^{\ell}_{|V||V|})^{{}^{\prime}}$,
we have

$\underline{\textbf{u}}_{\ell}=\Sigma_{\ell}\underline{\textbf{x}}^{\ell}\quad\forall\ell\in
V,$ (9)

where $\Sigma_{\ell}$ is a $|V|^{2}\times|V|^{2}$ matrix. The first row in
$\Sigma_{\ell}$ (corresponding to $h=1$) has all coefficients equal to 1 since
every cost in the sum is greater than $c_{(1)}$, the second row ($h=2$) has
all coefficients equal to 1 except for the coefficient corresponding to some
position $i_{1}j_{1}$ which is 0, and so until the last row ($h=|V|^{2}$),
that has all coefficients equal to 0 except for the coefficient corresponding
to some position $i_{|V|^{2}}j_{|V|^{2}}$ which is 1. Therefore,
$\Sigma_{\ell}$ has the following structure

$\Sigma_{\ell}=\,\bordermatrix{&\cdots&&i_{1}j_{1}&&\cdots&&i_{2}j_{2}&&\cdots&&i_{3}j_{3}&&\cdots&&i_{|V|^{2}}j_{|V|^{2}}&&\cdots\cr
h=1&\cdots&1&1&1&\cdots&1&1&1&\cdots&1&1&1&\cdots&1&1&1&\cdots\cr
h=2&\cdots&1&0&1&\cdots&1&1&1&\cdots&1&1&1&\cdots&1&1&1&\cdots\cr&\cdots&1&0&1&\cdots&1&0&1&\cdots&1&1&1&\cdots&1&1&1&\cdots\cr\vdots&\cdots&1&0&1&\cdots&1&0&1&\cdots&1&0&1&\cdots&1&1&1&\cdots\cr&&&\vdots&&&&\vdots&&\ddots&&\vdots&&&&\vdots&&\ddots\cr
h=|V|^{2}&\cdots&0&0&0&\cdots&0&0&0&\cdots&0&0&0&\cdots&0&1&0&\cdots\cr}.$
(10)

Consequently, $\Sigma_{\ell}$ can be rearranged through elemental matrix
transformations to an upper triangular matrix $\Sigma^{upper}_{\ell}$, so we
can rewrite system (9) as

$\underline{\textbf{u}}_{\ell}=\Sigma^{upper}_{\ell}\begin{pmatrix}x_{i_{1}j_{1}}^{\ell}\\\
x_{i_{2}j_{2}}^{\ell}\\\ \vdots\\\
x_{i_{|V|^{2}}j_{|V|^{2}}}^{\ell}\end{pmatrix}=\begin{pmatrix}1&1&1&\cdots&1&1\\\
0&1&1&\cdots&1&1\\\ 0&0&1&\cdots&1&1\\\ &&&\vdots&&\\\
0&0&0&\cdots&0&1\end{pmatrix}\begin{pmatrix}x_{i_{1}j_{1}}^{\ell}\\\
x_{i_{2}j_{2}}^{\ell}\\\ \vdots\\\
x_{i_{|V|^{2}}j_{|V|^{2}}}^{\ell}\end{pmatrix}.$ (11)

Therefore, $\Sigma_{\ell}$ has maximum range which implies that $f$ is an
injection and (9) defines for every $\ell\in V$ a single unique solution for
$x_{ij}^{\ell}$ variables for $i,j\in V$. A general expression for the inverse
of $\Sigma^{upper}_{\ell}$ can be given to obtain the solution for
$x_{ij}^{\ell}$ variables as follows

$\underline{\textbf{x}}^{\ell}=\begin{pmatrix}1&-1&0&\cdots&0&0\\\
0&1&-1&\cdots&0&0\\\ 0&0&1&\cdots&0&0\\\ &&&\vdots&&\\\ 0&0&0&\cdots&1&-1\\\
0&0&0&\cdots&0&1\end{pmatrix}\begin{pmatrix}u_{\ell 1}\\\ u_{\ell 2}\\\
\vdots\\\ u_{\ell|V|^{2}}\end{pmatrix},$ (12)

being the mapping $f^{-1}$ defined by the following relationship

$x_{i_{h}j_{h}}^{\ell}=\left\\{\begin{matrix}u_{\ell h}-u_{\ell
h+1}&h=1,\ldots,|V|^{2}-1,\\\ u_{\ell|V|^{2}}&h=|V|^{2}.\end{matrix}\right.$
(13)

Notice that constraints (3i) are needed in order for $f^{-1}$ to be well
defined. It can be verified that, in the case of no ties, $f^{-1}$ and $g$
coincide.

######  Property 3.6.

If no ties exists in the cost matrix $(c_{ij})_{i,j\in V}$, then $g=f^{-1}$.

###### Proof.

If $\ell\geq\ell(h)$, then $x_{ij}-\sum_{k<\ell}x_{ij}^{k}=\sum_{k\in
V}x_{ij}^{k}-\sum_{k<\ell}x_{ij}^{k}=\sum_{k\geq\ell}x_{ij}^{k}\geq
x_{i_{h}j_{h}}^{\ell}=u_{\ell h}-u_{\ell
h+1}\implies\min\left\\{x_{ij}-\sum_{k<\ell}x_{ij}^{k},u_{\ell
h}-u_{\ell,h+1}\right\\}=u_{\ell h}-u_{\ell,h+1}$. Otherwise, if
$\ell<\ell(h)$ or $x_{ij}=0$, trivially equal to 0. ∎

As a consequence, we get that
$g(P(\Omega^{\prime}_{u}))=P(\Omega^{\prime}_{x^{\ell}})$ when no ties exists
in the cost matrix.

###  3.3 Tree polytope description

This section extends the definition of the tree polytope $\mathcal{T}$
including some specific considerations that must be reviewed for the
application of each tree characterization within the OMT.

Formulation $F1_{x^{\ell}}^{\mathcal{T}}$ and $F1^{\mathcal{T}}_{u}$ assume
constraint $z\in\mathcal{T}$ to be included in the model. This constraint can
be replaced by any representation of the STP polytope, namely subtour
elimination, Miller-Tucker-Zemlim (MTZ), flow, etc. (see Magnanti and Wolsey,
1995, Fernández et al., 2017). Depending on the case, different variables must
be considered. The formulation in Miller et al. (1960) uses variables
$y_{ij}\in\\{0,1\\}$ for $(i,j)\in A$, which take value 1 if and only if arc
$(i,j)$ belongs to the modeled arborescence and continuous variables
$l_{i}\geq 0$ for $i\in V$, denoting the position that node $i$ occupies in
the arborescence respect to the root node. In the flow based formulation
introduced by Gavish (1983), continuous flow variables $f_{ij}\geq 0$ for
$(i,j)\in A$ are defined on the arcs of the directed network indicating the
amount of flow through arc $(i,j)$. The formulation proposed by Martin (1991)
models as many arborescences as network nodes using three index decision
variables $q_{kij}\in\\{0,1\\}$ for $(i,j)\in A$, which indicate whether or
not arc $(i,j)$ belongs to the arborescence rooted at $k$. In addition, each
tree polytope $\mathcal{T}$ includes constraint $\sum_{(i,j)\in E}z_{ij}=p-1$,
which ensures that the tree of facilities has exactly $p-1$ edges.

Some notation must be introduced in order to model $\mathcal{T}$. Given a
subset of nodes $S\subset V$, let us denote by $E(S)$ and $A(S)$ the subsets
of edges of $E$ and arcs of $A$ connecting nodes in $S$, i.e.,
$E(S)=\\{(i,j)\in E\ |\ i,j\in S\\}$ and $A(S)=\\{(i,j)\in A\ |\ i,j\in S\\}$.
The cut-set $\delta(S)$ associated with $S\subset V$ contains all edges with
one node in $S$ and the other node outside $S$, i.e. $\delta(S)=\\{(i,j)\in E\
|\ (i\in S,j\in V\setminus S)\ or\ (j\in S,i\in V\setminus S)\\}$.
Equivalently, in the directed network, the cut-set directed out of $S$ is
defined as $\delta^{+}(S)=\\{(i,j)\in A\ |\ i\in S,j\in V\setminus S\\}$ and
the cut-set directed into of $S$ is defined as $\delta^{-}(S)=\\{(i,j)\in A\
|\ j\in S,i\in V\setminus S\\}$.

In Table 3 we resume the main properties of the STP formulations that we have
considered. The criteria that have guided the selection of the formulations
are either their good theoretical properties or some characteristic that seems
useful as, for instance, a small number of variables or constraints. It is
well known that, as seen in the last column, from the formulations described
above $\mathcal{T}^{sub}$ and $\mathcal{T}^{km}$ hold the integrality
porperty, conversely to $\mathcal{T}^{mtz}$ and $\mathcal{T}^{flow}$.

Formulation | notation | main constraints | root | # vars | # const. | int
---|---|---|---|---|---|---
| Subtour
---
Edmonds (1970)
$\mathcal{T}^{sub}$ | $\displaystyle{\sum_{(i,j)\in E(S)}z_{ij}\leq|S|-1,\ S\neq\emptyset,S\subset V}$ |  | $O(|E|)$ | $Exp(|V|)$ | Yes
| Miller-Tucker-Zemlim
---
Miller et al. (1960)
$\mathcal{T}^{mtz}$ | $l_{j}\geq l_{i}+1-|V|(1-y_{ij}),\ (i,j)\in A$ | $r$ | $O(|E|)$ | $O(|E|)$ | No
| Flow
---
Gavish (1983)
$\mathcal{T}^{flow}$ | $\displaystyle{\sum_{(i,j)\in\delta^{+}(i)}f_{ij}-\sum_{(j,i)\in\delta^{-}(i)}f_{ji}=\left\\{\begin{matrix}p-1,&i=r\\\ -1,&i\in V\setminus\\{r\\}\end{matrix}\right.}$ | $r$ | $O(|E|)$ | $O(|E|)$ | No
| Kipp Martin
---
Martin (1991)
$\mathcal{T}^{km}$ | $\displaystyle{\sum_{(i,j)\in\delta^{+}(i)}q_{kij}\leq\left\\{\begin{matrix}1,&\ k\in V,i\in V:i\neq k\\\ 0,&\ k\in V,i=k\end{matrix}\right.}$ | $\forall k$ | $O(|V||E|)$ | $O(|V||E|)$ | Yes
Table 3: Main properties of the STP formulations considered.

As a consequence of the formulations comparison in Fernández et al. (2017), we
can state the relationship between the different formulations derived from the
combination of some sorting representations and tree polyhedra described
above. To this end, let $P_{xz}(\Omega_{\mathcal{S}}^{\mathcal{T}})$ be the
projected polytope onto the space of $x$ and $z$ of the linear relaxation of
an OMT formulation. Then, the following property holds:

######  Property 3.7.

$\displaystyle
P_{xz}(\Omega_{x^{\ell}}^{\mathcal{T}})=P_{xz}(\Omega_{u}^{\mathcal{T}}).$
(14) $\displaystyle
P_{xz}(\Omega_{\mathcal{S}}^{sub})=P_{xz}(\Omega_{\mathcal{S}}^{km})\subseteq\left\\{\begin{matrix}P_{xz}(\Omega_{\mathcal{S}}^{flow})\\\
\neq\\\ P_{xz}(\Omega_{\mathcal{S}}^{mtz}).\end{matrix}\right.$ (15)

###### Proof.

Is derived from the observations in Fernández et al. (2017). ∎

Regarding to $\mathcal{T}^{sub}$, note that the cardinality of the group of
subtour elimination constraints is exponential in the number of nodes. Since
many of these constraints are not needed to build the solution polytope, they
can be separated in polynomial time by solving a series of minimum cut-
problems. An effective branch-and-cut algorithm can be implemented to include
dynamically a certain number of these constraints, preventing from using the
entire set of subtour elimination constraints and reducing computational
effort. Furthermore, a cut-set based group of constraints can be introduced
replacing these constrains. Let $S\neq\emptyset,S\subset V$ be a connected
component of a solution in the previous algorithm, the following connection
cut can be defined:

$\displaystyle\sum_{(i,j)\in\delta^{+}(S)}x_{ij}+\sum_{(i,j)\in\delta^{-}(S)}x_{ij}+\sum_{(i,j)\in\delta(S)}z_{ij}\geq
1,$ $\displaystyle\forall S\neq\emptyset,S\subset V.$ (16)

This cut-set based connection cut implies that at least one allocation or one
edge from the tree of facilities must connect $S$ to a node of $V\setminus S$.

Regarding to $\mathcal{T}^{mtz}$, an arborescence is built rooted at a
arbitrarily selected root node $r\in V$, in which arcs follow the direction
from root to leaves. $\mathcal{T}^{flow}$ also relies on a source node $r\in
V$ which distributes the flow, but for the OMT, contrary to
$\mathcal{T}^{mtz}$, the choice of the root node is very influential as care
must be taken when spreading the flow. This selection can be done in two ways:
(1) adding a set of variables $r_{i}\in\\{0,1\\}$ for $i\in V$, that are equal
to 1 if the node $i\in V$ is selected as the source node for the tree of
facilities, or otherwise (2) arbitrarily selecting the source node and
distributing the flow along the tree, distinguishing whether the node selected
as the source is a facility or not.

If the source node is selected arbitrarily, in order to properly distribute
the flow units between facilities we must consider all possible scenarios for
the source node. If the source node is a non facility node, then it takes an
inflow of one unit and transfers $p-1$ units to the associated facility, so
the total units of distributed flow in the network are $p$. On the other hand,
if the source node is a facility, then it directly takes an inflow of $p-1$
units. All other nodes included in the tree have a demand of one unit of flow.

Therefore, the flow formulation using additional variables includes the
following group of constraints:

$\displaystyle\mathcal{T}^{flow1}:\sum_{i\in V}r_{i}=1$ (17a)
$\displaystyle\hskip 34.99677ptr_{i}\leq x_{ii}$ $\displaystyle i\in V$ (17b)
$\displaystyle\hskip
34.99677pt\sum_{(i,j)\in\delta^{+}(i)}f_{ij}-\sum_{(j,i)\in\delta^{-}(i)}f_{ji}=(p-1)r_{i}-(x_{ii}-r_{i})$
$\displaystyle i\in V$ (17c) $\displaystyle\hskip
34.99677ptf_{ij}\leq(p-1)z_{ij}$ $\displaystyle(i,j)\in E$ (17d)
$\displaystyle\hskip 34.99677ptf_{ji}\leq(p-1)z_{ij}$ $\displaystyle(i,j)\in
E.$ (17e)

On the other hand, the flow formulation without using additional variables
includes:

$\displaystyle\mathcal{T}^{flow2}:\sum_{(i,j)\in\delta^{+}(i)}f_{ij}-\sum_{(j,i)\in\delta^{-}(i)}f_{ji}=px_{ri}-x_{ii}$
$\displaystyle i\in V$ (18a) $\displaystyle\hskip
34.99677ptf_{ij}\leq(p-1)z_{ij}$ $\displaystyle(i,j)\in E$ (18b)
$\displaystyle\hskip 34.99677ptf_{ji}\leq(p-1)z_{ij}$ $\displaystyle(i,j)\in
E.$ (18c)

###  3.4 Alternative formulation

Previous $F1_{x^{\ell}}^{\mathcal{T}}$ and $F1^{\mathcal{T}}_{u}$ formulations
use the set of design variables $z$ to model a spanning tree connecting only
facilities. However, since the OMT assumes single client-facility allocation,
the tree structure of any OMT solution, uniquely determined by the allocation
($x$) and design ($z$) variables, is globally preserved. This is, considering
both the facilities tree and the allocations of clients to their corresponding
facilities, we also obtain a larger tree where clients are at the end nodes.
This rationale allow us to provide an alternative formulation that models an
OMT solution designing a spanning tree over the complete set of nodes $V$.
Holding the definition of variables $x$ and $x^{\ell}$ as before, let now
$z_{ij}\in\\{0,1\\}$ for $(i,j)\in E$, be equal to 1 if $(i,j)$ is an edge
connecting either facilities or client-facility pairs, zero otherwise. With
this new definition of the $z$ variables, we can reformulate
$F1_{x^{\ell}}^{\mathcal{T}}$ as follows:

$\displaystyle\hskip
28.45274ptF2_{x^{\ell}}^{\mathcal{T}}:\min\quad\frac{1}{\displaystyle{\sum_{\ell\in
V}\lambda_{\ell}}}\sum_{\ell\in V}\sum_{(i,j)\in
A}\lambda_{\ell}c_{ij}x_{ij}^{\ell}+\frac{1}{p-1}\sum_{(i,j)\in
E}c_{ij}(z_{ij}-x_{ij}-x_{ji})$ (19a) $\displaystyle\textrm{s.t.:}\hskip
7.11317pt\sum_{i\in V}x_{ii}=p$ (19b) $\displaystyle\hskip
34.99677pt\sum_{j\in V}x_{ij}=1$ $\displaystyle i\in V$ (19c)
$\displaystyle\hskip 34.99677pt2x_{ij}\leq 1-x_{ii}+x_{jj}$
$\displaystyle(i,j)\in A:i\neq j$ (19d) $\displaystyle\hskip
34.99677ptx_{ij}+x_{ji}\leq z_{ij}$ $\displaystyle(i,j)\in E$ (19e)
$\displaystyle\hskip 34.99677pt2z_{ij}\leq x_{ii}+x_{jj}+x_{ij}+x_{ji}$
$\displaystyle(i,j)\in E$ (19f) $\displaystyle\hskip
34.99677ptz_{ij}\in\mathcal{T}$ $\displaystyle(i,j)\in E$ (19g)
$\displaystyle\hskip 34.99677ptx_{ij}=\sum_{\ell\in V}x_{ij}^{\ell}$
$\displaystyle(i,j)\in A$ (19h) $\displaystyle\hskip 34.99677pt\sum_{(i,j)\in
A}x_{ij}^{\ell}=1$ $\displaystyle\ell\in V$ (19i) $\displaystyle\hskip
34.99677pt\sum_{(i,j)\in A}c_{ij}x_{ij}^{\ell}\leq\sum_{(i,j)\in
A}c_{ij}x_{ij}^{\ell+1}$ $\displaystyle\ell\in V:\ell<|V|$ (19j)
$\displaystyle\hskip 34.99677ptx_{ij}\in\\{0,1\\}$ $\displaystyle(i,j)\in A$
(19k) $\displaystyle\hskip 34.99677ptx_{ij}^{\ell}\in\\{0,1\\}$
$\displaystyle(i,j)\in A,\ell\in V$ (19l) $\displaystyle\hskip
34.99677ptz_{ij}\in\\{0,1\\}$ $\displaystyle(i,j)\in E.$ (19m)

The objective function (19a) is similar to $F1_{x^{\ell}}^{\mathcal{T}}$, but
needs to be modified in order to consider only the design cost of the part of
the tree connecting facilities, this is, subtracting the associated cost to
the edges allocating clients to facilities to the total tree design cost. Now,
Constraints (19d) guarantee that client-facility allocations are only possible
if $i$ is a client and $j$ is a facility. Note that, these constraints result
from unification of two simpler group of constraints $x_{ij}\leq 1-x_{ii}$ and
$x_{ij}\leq x_{jj}$ for $(i,j)\in A:i\neq j$. Constraints (19e) ensure that
only one allocation, client $i$ to facility $j$ or vicerversa, can be
considered if there exists an edge connecting $i,j\in V$. In this sense,
constraints (19f) impose that the only possibilities in which a tree edge can
be selected are if both $i$ or $j$ are facilities or if $i$ is a client and
$j$ its facility, or viceversa. The remaining constraints hold unvarying.

For this approach, similar $\mathcal{T}$ descriptions as in Section 3.3 can be
considered, but the adaptation is straightforward since the main
characteristic to model in this formulation is the tree. Now, the cut-set
based group of constraints are simpler, $\sum_{(i,j)\in\delta(S)}z_{ij}\geq
1$, and for the flow formulation it is not necessary to differentiate whether
the arbitrary source node selection is a facility or not, reducing
formulations complexity. Formulation $F2_{u}^{\mathcal{T}}$ for covering
variables using this alternative approach is left to the reader.

###  3.5 Benders decomposition

The OMT can be solved by using a Benders decomposition framework (see Benders,
1962) that we briefly describe in this section. In the classical Benders
decomposition algorithm, the original mixed integer problem is divided into
two problems, a master problem (MP) and a subproblem (SP), that are solved
iteratively. The two problems are related, so the outcome of one directly
modifies the outcome of the other. First, the MP is solved to obtain the
values of certain fixed variables; with these, we can then solve the SP. Once
the SP has been solved, either new feasibility or new optimality cuts are
introduced within the MP until the lower and upper bounds coincide. For the
OMT, it arises to use DOMP as MP and MST as SP. For instance, we can
illustrate the MP via $F1_{x^{\ell}}^{\mathcal{T}}$ as follows:

$\displaystyle\hskip
28.45274ptF^{MP}:\min\quad\frac{1}{\displaystyle{\sum_{\ell\in
V}\lambda_{\ell}}}\sum_{\ell\in V}\sum_{(i,j)\in
A}\lambda_{\ell}c_{ij}x_{ij}^{\ell}+\mu$ (20a)
$\displaystyle\textrm{s.t.:}\hskip
7.11317pt(\ref{OMT_f1_c1})-(\ref{OMT_f1_c3}),(\ref{OMT_f1_c6})-(\ref{OMT_f1_c10})$
(20b) $\displaystyle\hskip 34.99677pt\mu\geq 0.$ (20c)

Similar descriptions for $F^{MP}$ can be introduced using other formulations
in Section 3.1.

In a classical Benders decomposition framework, the MP is solved to optimality
keeping both the objective function, which can be split into the sum of the
DOMP objective plus the $\mu$ term, and the variables representing the
facilities selected, $\bar{x}=\\{x_{ii}\ |\ x_{ii}=1,\forall i\in V\\}$. If
possible, the lower bound is updated using the MP objective. Thereafter, the
SP sets as facilities the previously $\bar{x}$ identified in the MP solution
and, if possible, the upper bound using the (weighted) sum of the DOMP plus
the SP objectives is updated. Finally, in any case, a optimality cut
($Opt.cut$) is added to the MP. This procedure is repeated until both upper
and lower bounds coincide.

For the OMT, the SP is solved by means of a Kipp Martin ($km$) MST dual
formulation (see Labbé et al. (2021) for details on the implementation). This
$km$ MST formulation and its dual form are adapted to the OMT structure as
follows:

$\displaystyle\hskip 28.45274ptF^{km}:\min\sum_{(i,j)\in E}c_{ij}z_{ij}$ (21a)
$\displaystyle\hskip 34.99677ptz_{ij}\leq\bar{x}_{ii}$ $\displaystyle(i,j)\in
E$ (21b) $\displaystyle\hskip 34.99677ptz_{ij}\leq\bar{x}_{jj}$
$\displaystyle(i,j)\in E$ (21c) $\displaystyle\hskip 34.99677pt\sum_{(i,j)\in
E}z_{ij}=p-1$ (21d) $\displaystyle\hskip
34.99677pt\sum_{\begin{subarray}{c}(i^{\prime},j)\in E:\\\ (i^{\prime}=k\wedge
j=i)\\\ \lor\\\ (i^{\prime}=i\wedge
j=k)\end{subarray}}z_{i^{\prime}j}+\sum_{(i,j)\in A:j\neq k}q_{kij}\leq 1$
$\displaystyle k,i\in V:i\neq k$ (21e) $\displaystyle\hskip
34.99677ptq_{kij}+q_{kji}=z_{ij}$ $\displaystyle k\in V,(i,j)\in E:i,j\neq k$
(21f) $\displaystyle\hskip 34.99677ptz_{ij}\geq 0$ $\displaystyle(i,j)\in E$
(21g) $\displaystyle\hskip 34.99677ptq_{kij}\geq 0$ $\displaystyle k\in
V,(i,j)\in E.$ (21h)

$\displaystyle\hskip 28.45274ptF^{SP}:\max\alpha(p-1)-\sum_{k,i\in V:i\neq
k}\beta_{ki}-\sum_{(i,j)\in E}(\bar{x}_{ii}\tau_{ij}+\bar{x}_{jj}\eta_{ij})$
(22a) $\displaystyle\hskip 34.99677pt\alpha-\beta_{ij}-\beta_{ji}-\sum_{k\in
V:k\neq i,j}\gamma^{k}_{ij}-\tau_{ij}-\eta_{ij}\leq c_{ij}$
$\displaystyle(i,j)\in E$ (22b) $\displaystyle\hskip
34.99677pt-\beta_{ki}+\sum_{\begin{subarray}{c}(i^{\prime},j^{\prime})\in
E:\\\ (i^{\prime}=i\wedge j^{\prime}=j)\\\ \lor\\\ (i^{\prime}=j\wedge
j^{\prime}=i)\end{subarray}}\gamma^{k}_{i^{\prime}j^{\prime}}\leq 0$
$\displaystyle k\in V,(i,j)\in E:i,j\neq k$ (22c) $\displaystyle\hskip
34.99677pt\alpha\in\mathbb{R}$ (22d) $\displaystyle\hskip
34.99677pt\beta_{ki}\geq 0$ $\displaystyle k,i\in V:i\neq k$ (22e)
$\displaystyle\hskip 34.99677pt\gamma^{k}_{ij}\in\mathbb{R}$ $\displaystyle
k\in V,(i,j)\in E:i,j\neq k$ (22f) $\displaystyle\hskip
34.99677pt\tau_{ij}\geq 0$ $\displaystyle(i,j)\in E$ (22g)
$\displaystyle\hskip 34.99677pt\eta_{ij}\geq 0$ $\displaystyle(i,j)\in E.$
(22h)

Observe that, constraints (2e) are presented as disaggregated constraints
(28b)-(28c) in the SP because, although it has been computationally proven to
report worse results, dealing with continuous $z$ variables force to use the
disaggregated formulation. In this way, the $Opt.cut$ introduced have the
following expression:

$Opt.cut:\ \frac{1}{p-1}\Big{[}\bar{\alpha}(p-1)-\sum_{k,i\in V:i\neq
k}\bar{\beta}_{ku}-\sum_{(i,j)\in
E}(x_{ii}\bar{\tau}_{ij}+x_{jj}\bar{\eta}_{ij})\Big{]}\leq\mu.$ (23)

Note that in every iteration, only one $Opt.cut$ is added. For the general
Benders framework, some authors (see, e.g., Fischetti et al., 2010) force the
addition of feasibility cuts even when the MP is feasible to boost the
algorithm. In our case, since our SP is always feasible, it is not necessary
to introduce feasibility cuts.

The classical Benders decomposition can be introduced into a branch-and-cut
framework (or modern Benders approach), also known as branch-and-Benders-cut,
for a more efficient performance as illustrated in Algorithm 3. In this
algorithm we initialize the tree $\mathfrak{T}$, considering solving the MP at
the root node, and an empty pool of cuts $\mathcal{P}$. Once solved the MP at
the root node, we start the branching procedure. If at a particular node of
the process the solution found is fractional, keep branching. Otherwise, when
an integer solution is found, the lower bound is updated using the MP
objective value of the current node $o^{\prime}\in\mathfrak{T}$, the SP is
solved fixing the facilities $\bar{x}$ obtained in the MP solution, the upper
bound is updated if possible and the optimality constraint $Opt.cut$ is added
to a pool $\mathcal{P}$ of cuts. The cuts from pool $\mathcal{P}$ are then
included for the MP solution in other nodes of $\mathfrak{T}$.

1 Set tree $\mathfrak{T}=\\{o\\}$, where $o=F^{MP}$ has no branching
constraints

2 Initialize a pool of cuts $\mathcal{P}=\emptyset$

3 while  _$\mathfrak{T}$ is nonempty_ do

4 Select a node $o^{\prime}\in\mathfrak{T}$

5 $\mathfrak{T}:=\mathfrak{T}\,\backslash\\{o^{\prime}\\}$

6 Solve $o^{\prime}$ considering $\mathcal{P}$ $\rightarrow\bar{x}$

7 if  _$\bar{x}$ is fractional_ then

8 Branch, resulting in nodes $o^{\prime\prime}$ and $o^{\prime\prime\prime}$

9
$\mathfrak{T}:=\mathfrak{T}\cup\\{o^{\prime\prime},o^{\prime\prime\prime}\\}$

10 else

11 Solve $F^{SD}\rightarrow(\bar{\alpha},\bar{\beta},\bar{\tau},\bar{\eta})$

12 Add optimality constraint $Opt.cut$ to $\mathcal{P}$

13 $\mathfrak{T}:=\mathfrak{T}\cup\\{o^{\prime}\\}$

14

15

16

Algorithm 1 OMT branch-and-Benders-cut

This allows to use different strategies for producing the optimality cuts. For
instance, these cuts can be generated in every feasible node, only in those
nodes that have improved the lower bound beyond a predefined threshold or only
when incumbent solutions are found along the search process. If caution is not
taken, too many unnecessary cuts can be produced slowing down the attainment
of a MP solution instead of speeding it up. Also, in the classical Benders
decomposition, every $Opt.cut$ added implies solving to optimality a MP, which
is computationally costly. In the modern approach, the pool of cuts
$\mathcal{P}$ considered in a specific node of the branch-and-cut procedure
may contain cuts that have already been identified, slowing down the
efficiency since it would reintroduce repeated cuts when branching at
different levels of the search tree. For these reasons, it could be helpful to
consider a strategy to initialize the pool of cuts $\mathcal{P}$ prior to
starting the procedures using a so called warm-start phase (see, e.g., Martins
de Sa et al., 2013). The interest behind this warm phase is to be able to
introduce a certain number of cuts at low cost before start branching. In
order to introduce this cuts, the solution in the warm-start phase does not
need to be computed to optimality, is enough to obtain a feasible solution.
Furthermore, a procedure to build cuts from fractional values of the variables
can be implemented. More details can be found on Appendix A.

The presented branch-and-Benders approach has DOMP as a subproblem which is
more difficult than MSTP. Therefore, this branch-and-Benders implies solving a
DOMP adding optimality Benders cuts (costly to obtain) what seems to be less
efficient than solving a DOMP with some MSTP additional constraints. Thus,
this general technique for solving the OMT would require an alternative way
for solving DOMP, may be applying a nested Benders decomposition. In any case,
this analysis is out of the scope of this paper.

##  4 Improvements

###  4.1 Initial solution

The branching processes used as an underlying framework to solve the presented
formulations usually take a considerable amount of time in finding an initial
feasible solution (upper bound). For this reason, in this section we introduce
two OMT heuristic algorithms to compute an initial solution.

  * •

DOMP + MST heuristic. This approach performs first the DOMP and, once the
facilities have been assigned and compensated, they are fixed for searching a
MST connecting those facilities in polynomial time using Kruskal MST
algorithm.

  * •

PMEDT + DOMP heuristic. This approach finds $p$ facilities and the tree
structure computing the PMEDT by means of a MST competitive formulation, for
example the MTZ formulation. Both, facilities and the tree structure, are left
fixed and the reassignment of clients to facilities is then performed using
the DOMP. This algorithm has been proven to be more efficient providing an
initial solution.

###  4.2 Variable fixing

This section addresses the description of some preprocessing steps to reduce
the size of the covering formulation $F1^{\mathcal{T}}_{u}$ in order to
improve its efficiency. These variable fixing procedures are based on
adaptations of some arguments already used in Puerto et al. (2011, 2013) and
Pozo et al. (2021) where fixing a certain number of variables improved the
efficiency of the formulations.

Given the ordered sequence of unique costs and the sorting factor of the
orders $\ell$, the $u_{\ell h}$-variables matrix is expected to have a
specific step structure. It might be expected that for small values of $h$,
the number of allocations at cost smaller than $c_{(h)}$ should be small and
therefore $u_{\ell h}=1$ in the left-bottom part of the $u$-matrix from a
certain $\ell$ to the end. Similarly, it might also be expected that many
$u_{\ell h}$-variables in the right-upper part of the $u$-matrix will take
value 0 in the optimal solution. Indeed, $u_{\ell h}=0$ means that the
$\ell$-th sorted allocation cost is less than to $c_{(h)}$, which is very
likely to be true if $h$ is sufficiently large and $\ell$ is small enough. For
example, since $c_{jj}=0$ for $j\in V$, we have that $u_{\ell h}=0$ for
$\ell\in\\{1,\ldots,p\\},h\in H$. These preprocessings aim to fix as many of
this $u_{\ell h}$-variables as possible.

####  4.2.1 Preprocessings for fixing variables to 1

Given a $h\in H$, in order to fix $u_{\ell h}$-variables to 1 we deal with an
auxiliary problem that maximizes the number of allocations satisfying
$c_{ij}\leq c_{(h-1)}$, which is equivalent to the number of variables that
can assume a 0 value, or what is the same, this will provide the number of
allocations satisfying the opposite ($c_{ij}>c_{(h-1)}\equiv c_{ij}\geq
c_{(h)}$) and, therefore, the minimum number of $u_{\ell h}$-variables that
can assume value of 1. Using the variables previously defined, the formulation
of this problem is:

$\displaystyle\hskip 28.45274ptF^{pre}_{1}:\max H_{h}^{1}:=\sum_{i\in
V}\sum_{j\in V}x_{ij}$ (24a) $\displaystyle\textrm{s.t.:}\hskip
7.11317pt\sum_{i\in V}x_{ii}=p$ (24b) $\displaystyle\hskip
34.99677pt\sum_{j\in V}x_{ij}\leq 1$ $\displaystyle\forall i\in V$ (24c)
$\displaystyle\hskip 34.99677ptx_{ij}\leq x_{jj}$ $\displaystyle\forall i,j\in
V:i\neq j$ (24d) $\displaystyle\hskip 34.99677ptc_{ij}x_{ij}\leq c_{(h-1)}$
$\displaystyle\forall i,j\in V$ (24e) $\displaystyle\hskip
34.99677ptx_{ij}\in\\{0,1\\}$ $\displaystyle\forall i,j\in V.$ (24f)

$F^{pre}_{1}$ gives the maximum number (in the worst case) of allocations
realized at a cost less than or equal to $c_{(h-1)}$. If $H_{h}^{1}$ is the
optimal value of problem above, since there are $|V|=N$ total possible
allocations, the number of allocations satisfying $c_{ij}\geq c_{(h)}$ must be
necessarily greater than or equal to $N-H_{h}^{1}$, or equivalently, in any
feasible solution of a covering formulation:

$u^{\ell}_{h}=1,\quad\forall\ell\in\\{H_{h}^{1}+1,\ldots,N\\}.$

####  4.2.2 Preprocessings for fixing variables to 0

Also, for a given $h\in H$, to fix the maximum number of $u_{\ell
h}$-variables possible to 0 we deal with the following auxiliary problem:
maximize the number of allocations satisfying $c_{ij}\geq c_{(h)}$, which will
provide the minimum number of 0 that the $h$-th column of the $u$-matrix must
have. Using the variables defined previously, the formulation of this problem
is:

$\displaystyle\hskip 28.45274ptF^{pre}_{0}:\max H_{h}^{0}:=\sum_{i\in
V}\sum_{j\in V}x_{ij}$ (25a) $\displaystyle\textrm{s.t.:}\hskip
7.11317pt\sum_{i\in V}x_{ii}=p$ (25b) $\displaystyle\hskip
34.99677pt\sum_{j\in V}x_{ij}\leq 1$ $\displaystyle\forall i\in V$ (25c)
$\displaystyle\hskip 34.99677ptx_{ij}\leq x_{jj}$ $\displaystyle\forall i,j\in
V:i\neq j$ (25d) $\displaystyle\hskip 34.99677ptc_{ij}\geq c_{(h)}x_{ij}$
$\displaystyle\forall i,j\in V:i\neq j$ (25e) $\displaystyle\hskip
34.99677ptx_{ij}\in\\{0,1\\}$ $\displaystyle\forall i,j\in V.$ (25f)

In this problem, for constraints (25e) we could not consider allocations
$x_{ii}$ for $i\in V$, as considered in Puerto et al., 2011, Puerto et al.,
2013 and Pozo et al., 2021 among others, because in such case our problem is
not feasible. Infeasibility is due to having to consider constraints (25b)
together with constraints (25e). If we consider allocations such $x_{ii}$ for
$i\in V$ we have $c_{ii}=0$ and since $c_{(h)}>0$ for $h\in H$, constraints
(25e) set all $x_{ii}$ to 0, which is not compatible with constraints (25b).
For this reason we must impose $i,j\in V:i\neq j$ in (25e).

For a given $h\in H$, $F^{pre}_{0}$ is the maximum number of allocations done
at a cost greater than or equal to $c_{(h)}$. Therefore, if $H^{0}_{h}$ is the
optimal value of problem above, the $h$-th column of the $u$-matrix must have
at least $N-H^{0}_{h}$ zeros. As we know that exactly the $p$ first rows of
the $u$-matrix can be fixed to 0, which corresponds to the allocations of the
facilities to itselves at a cost 0 not considered in the constraints (25e), in
any feasible solution of the covering formulation satisfies:

$u^{\ell}_{h}=0,\quad\forall\ell\in\\{1,\ldots,N-H^{0}_{h}+p\\}.$

For the ease of understanding, an example can be found in Appendix B.

##  5 Computational experiments

This section reports on the results of some computational experiments
performed in order to empirically compare the proposed OMT formulations. Table
4 catalogs all different formulations considering every combination for the
tree polytope $\mathcal{T}\in\\{sub,mtz,flow,km\\}$, sorting type
$\mathcal{S}\in\\{x^{\ell},u\\}$ and whether $\mathcal{T}$ is built between
facilities or in $V$. The interested reader can see Appendix C for the whole
catalogue of formulations described in detail.

$\mathcal{T}$ | $\mathcal{S}$ |  (1): $\mathcal{T}$ in facilities |  (2): $\mathcal{T}$ in $V$
---|---|---|---
$sub$ | $x^{\ell}$ |  $F1_{x^{\ell}}^{sub1}$, $F1_{x^{\ell}}^{sub2}$ |  $F2_{x^{\ell}}^{sub1}$, $F2_{x^{\ell}}^{sub2}$
$u$ |  $F1_{u}^{sub1}$, $F1_{u}^{sub2}$ |  $F2_{u}^{sub1}$, $F2_{u}^{sub2}$
$mtz$ | $x^{\ell}$ | $F1_{x^{\ell}}^{mtz}$ | $F2_{x^{\ell}}^{mtz}$
$u$ | $F1_{u}^{mtz}$ | $F2_{u}^{mtz}$
$flow$ | $x^{\ell}$ |  $F1_{x^{\ell}}^{flow1}$, $F1_{x^{\ell}}^{flow2}$ |  $F2_{x^{\ell}}^{flow1}$, $F2_{x^{\ell}}^{flow2}$
$u$ |  $F1_{u}^{flow1}$, $F1_{u}^{flow2}$ |  $F2_{u}^{flow1}$, $F2_{u}^{flow2}$
$km$ | $x^{\ell}$ | $F1_{x^{\ell}}^{km}$ | $F2_{x^{\ell}}^{km}$
$u$ | $F1_{u}^{km}$ | $F2_{u}^{km}$
Table 4: OMT formulations summary.

For the computational study, instances $G=(V,E)$ are generated as complete
networks of sizes $|V|\in\\{20,30,40,50,60,70,80,90,100\\}$ with random
integer costs $c_{ij}$ following a uniform distribution in $[1,1e5]$. In order
to follow the structure of previous published works, where other ordered
median problems were considered, the number of facilities for each group of
instances is chosen as
$p\in\\{\lfloor\frac{N}{4}\rfloor,\lfloor\frac{N}{3}\rfloor,\lfloor\frac{N}{2}\rfloor\\}$.
Also, we test three commonly studied criteria for the $\lambda$ scaling factor
values:

  * •

median criterion: $\lambda=\underbrace{(1,1,....,1)}_{|V|}$.

  * •

$k$-centrum criterion:
$\lambda=(\underbrace{0,...,0}_{\lfloor\frac{2}{3}|V|\rfloor},\underbrace{1,...,1}_{|V|-\lfloor\frac{2}{3}|V|\rfloor})$.

  * •

$k$-trimmed mean criterion:
$\lambda=(\underbrace{0,...,0}_{\lfloor\frac{1}{3}|V|\rfloor},\underbrace{1,...,1}_{|V|-\lfloor\frac{2}{3}|V|\rfloor},\underbrace{0,...,0}_{\lfloor\frac{1}{3}|V|\rfloor})$.

In all tables, results correspond to groups of 5 instances with same $(|V|,p)$
pair. This gives a benchmark of 135 instances in total. We present average
results for each group of instances. All instances were solved with Gurobi
9.1.1 optimizer, under a Windows 10 environment in an Intel(R) Core(TM)
i7-2600 CPU 3.40 GHz processor and 16 GB RAM. The CPU time limit fixed for
solving each instance is 3600 seconds.

Tables are grouped in blocks. The first block contains the values of the
instances parameters, namely $|V|$ and $p$. Then, we give a block of 6 columns
for each formulation with the following information:

  * •

Columns $|\\#|$ indicate the number of instances in the group that could be
solved to optimality within the CPU time limit.

  * •

Columns $g\overline{U}R\ $give the percentage relative root gap, computed as
$100\frac{obj_{\overline{U}}\ -\ obj_{R}}{obj_{\overline{U}}}$, where
$obj_{\overline{U}}$ denotes the best known upper bound obtained in all our
experiments and $obj_{R}$ denotes the optimal value of the linear relaxation
at the root node.

  * •

Columns $g\overline{U}L\ $give the percentage relative lower bound gap,
computed as $100\frac{obj_{\overline{U}}\ -\ obj_{L}}{obj_{\overline{U}}}$,
where $obj_{L}$ denotes the lower bound at termination.

  * •

Columns $gU\overline{L}\ $give the percentage relative upper bound gap,
computed as $100\frac{obj_{U}-obj_{\overline{L}}}{obj_{U}}$, where $obj_{U}$
denotes the upper bound at termination and $obj_{\overline{L}}$ denotes the
best known lower bound obtained in all our experiments.

  * •

Columns $gUL\ $give the percentage relative gap at termination, computed as
$100\frac{obj_{U}-obj_{L}}{obj_{U}}$.

  * •

Columns $nod$ indicate the average number of nodes explored in the branch-and-
bound ($B\&B$) search tree.

Note that, while $g\overline{U}R\ $and $g\overline{U}L\ $provide quality
measures of the lower bounds (at the root node and at termination,
respectively), $gU\overline{L}\ $provides a quality measure of the upper
bounds. In addition, $gUL\ $provides a measure of both upper and lower bounds
for the average performance. If the reported value of $gUL\ $is 0 then all
instances were solved to optimality. Along all experiments we give as initial
solutions those coming from the heuristics developed in Section 4, so in all
cases it is possible to find at least a feasible solution.

The caption just above each block gives the formulation the block refers to.
Due to the large number of formulations (see Table 4), we decided to report
just four final formulations. This choice was based on preliminary
computational result based on different set of instances. We report results
among $F1^{(\mathcal{T})}_{(\mathcal{S})}$ with
$\mathcal{S}\in\\{x^{\ell},u\\}$ and $\mathcal{T}\in\\{mtz,flow1,flow2,km\\}$
since other approaches (subtour elimination, Benders decomposition and
$F2^{(\cdot)}_{(\cdot)}$) were clearly outperformed in our preliminary tests,
especially for large instance sizes. All preliminary results are available in
Appendix D. Then, the criteria that have guided us to present as final
formulations $F1_{x^{\ell}}^{mtz}$, $F1_{x^{\ell}}^{flow1}$, $F1_{u}^{mtz}$
and $F1_{u}^{km}$ are the following:

  1. 1.

Over a total of four formulations we have chosen two types of
$F1_{x^{\ell}}^{(\cdot)}$ formulations and two types of $F1_{u}^{(\cdot)}$
formulations. We recall that $F1_{u}^{(\cdot)}$ takes advantage of ties in the
cost matrix (see Section 3.1). Besides, choosing formulations among
$F1_{x^{\ell}}^{(\cdot)}$ requires an analysis of the gap left (many instances
could not be solved in the time limit) and choosing formulations among
$F1_{u}^{(\cdot)}$ requires an analysis of the running time (mostly all
instances were solved within the time limit).

  2. 2.

According to Table 5, $F1_{x^{\ell}}^{flow1}$ slightly outperforms to its
variant $F1_{x^{\ell}}^{flow2}$.

  3. 3.

According to Table 5, $F1_{x^{\ell}}^{mtz}$ slightly outperforms
$F1_{x^{\ell}}^{km}$.

  4. 4.

According to performance profiles in Figure 4, $F1_{u}^{km}$ has shown the
best performance among all $F1_{u}^{(\cdot)}$ formulations, specially in the
$k$-trimmed mean criterion and $k$-centrum criterion (larger instances).

  5. 5.

Finally, $F1_{u}^{mtz}$ has been chosen so that the reader could have a
comparison of the same tree polytope description among both sorting
descriptions, that is, by means of $F1_{x^{\ell}}^{mtz}$ and $F1_{u}^{mtz}$.
Beyond that, we are interested in reporting $F1_{(\cdot)}^{mtz}$ since $mtz$
has been shown as a promising tree polytope description for being combined
with sorting constraints (see Fernández et al., 2014).

$\mathcal{T}$ | median |  $k$-centrum |  $k$-trimmed mean
---|---|---|---
| $gUL\ $ | $|\\#|$ | $gUL\ $ | $|\\#|$ | $gUL\ $ | $|\\#|$
$mtz$ | 1.26 | 57 | 27.14 | 3 | 9.59 | 30
$flow1$ | 0.53 | 57 | 25.12 | 4 | 8.85 | 32
$flow2$ | 0.65 | 57 | 25.9 | 3 | 9.58 | 32
$km$ | - | 60 | 28.47 | 3 | 10.19 | 33
Table 5: $F1_{x^{\ell}}^{\mathcal{T}}$ formulations comparison for the three
different criteria Figure 4: $F1_{u}^{(.)}$ formulations comparison for the
three different criteria

A general overview of the OMT computational experience brings some common
observations for all criteria. A first significant evidence is that, as a
consequence of Property 3.2, values for $g\overline{U}R\ $are equal for every
$(|V|,p)$ pair. Reported values of $g\overline{U}L\ $, $gU\overline{L}\ $and
$gUL\ $are smaller for $F1^{(\cdot)}_{u}$ formulations, concluding that
$F1^{(\cdot)}_{x^{\ell}}$ formulations are clearly outperformed in these
terms. Moreover, $F1^{(\cdot)}_{u}$ formulations are able to certify
optimality for most of the instances. Concerning $gUL\ $values, instances with
lower $p$ are rather more difficult to solve in general terms than those with
bigger $p$ values. Besides, $nod$ parameter is influenced by how well the
problem is described (formulation used, number of fixed variables) and the
number of variables and constraints introduced. Starting from the smaller size
instances, formulations tend to increase $nod$ values as long as they increase
their size. However, at some point $nod$ values start decreasing when
variables and constraints considerably increase and computations at each node
are more time-consuming. To sum up, for $F1^{(\cdot)}_{u}$ formulations, $km$
reports better results than $mtz$ until a certain instance size, which depends
on the criteria, and afterwards $mtz$ starts attaining better results due to
the size increment of the $km$ formulation. Therefore, we conclude that
$F1_{u}^{mtz}$ is, in general, the formulation providing better results.

We now comment on some specific considerations regarding each criterion. In
Table 6, where results for median criterion are reported, all instances reach
optimality for $F1^{(\cdot)}_{x^{\ell}}$ formulations when $|V|\leq 50$ and
for $F1^{(\cdot)}_{u}$ formulations when $|V|\leq 70$. However,
$F1^{(\cdot)}_{u}$ are always able to certify optimality for at least one of
the instances. For the median criterion, values for $g\overline{U}R\ $range
between $29\%-42\%$. Concerning $nod$ values, $F1^{(\cdot)}_{x^{\ell}}$
formulations tend to explore more nodes of the $B\&B$ tree for small size
instances than $F1^{(\cdot)}_{u}$ formulations. This exploration is gradually
increased until $|V|=70$, where computations at each node require more time.
On the other hand, $F1^{(\cdot)}_{u}$ formulations need to explore less nodes
in order to certify optimality. As shown in previous DOMP problems, median
criterion does not reflect the computational complexity of the sorting problem
since all lambdas are equal to 1. In Tables 7 and 8, where results for
$k$-centrum criterion and $k$-trimmed mean criterion are respectively
reported, problems to prove optimality start to appear for smaller size
instances, being specially difficult for the $k$-centrum criterion. For this
criteria, $g\overline{U}R\ $, $g\overline{U}L\ $, $gU\overline{L}\ $and $gUL\
$values are greater than those reported for median criterion. Moreover, for
$k$-centrum and $k$-trimmed mean, formulations tend to need to explore more
$B\&B$ nodes for small size instances than for median criterion and are not
able to explore many nodes for large size instances. Therefore, we can
conclude that, as expected, our formulations perform better for median
criterion than for $k$-trimmed mean, and specially $k$-center criterion
reports the worst results.

##  6 Conclusions

In this paper we consider the OMT, that is a single-allocation location
problem where $p$ facilities must be placed on a network and connected by a
non-directed tree. The OMT is a complex network design problem that involves a
number of components (network connectivity and sorting of allocation costs)
each of which defines by itself a hard combinatorial optimization problem. The
in/exclusion of these components give rise to different subproblems of the OMT
that are well-known problems of the literature. We have presented several
formulations based on the minimum spanning tree and ordered median properties,
as the use of covering variables. In order to improve formulations performance
we introduce a series of improvements via providing an initial solution and
the development of two preprocessings that reduce the size of covering
formulations. We have also developed a Benders decomposition algorithm, which
arises naturally in our problem, although it did not improve results of the
exact formulations. Finally, we derive extensive computational results
comparing in detail the different formulations, enhancements and solution
techniques provided.

## Acknowledgements

This research was supported by the project "Nuevos resultados sobre los
problemas de diseño y optimización en redes complejas: Aplicaciones al diseño
de ciudades inteligentes" (Proyecto I+D+i FEDER Andalucía, reference
US-1256951), "Retos de la optimización combinatoria en los nuevos modelos de
redes complejas y ciencia de datos" (Proyecto I+D+i Junta de Andalucía,
reference P18-FR-1422), "Optimization on data science and network design
problems: Large scale network models meet optimization and data science tools"
(Plan Estatal 2017-2020 Generación Conocimiento - Proyectos I+D+i, reference
PID2020-114594GB-C21) and "Complex networks meet data science" (Proyectos
Fundación "BBVA"). This support is gratefully acknowledged.

| $F1_{x^{\ell}}^{mtz}$ | $F1_{x^{\ell}}^{flow1}$ | $F1_{u}^{mtz}$ | $F1_{u}^{km}$
---|---|---|---|---
$|V|$ | $p$ | $|\\#|$ | $g\overline{U}R\ $ | $g\overline{U}L\ $ | $gU\overline{L}\ $ | $gUL\ $ | $nod$ | $|\\#|$ | $g\overline{U}R\ $ | $g\overline{U}L\ $ | $gU\overline{L}\ $ | $gUL\ $ | $nod$ | $|\\#|$ | $g\overline{U}R\ $ | $g\overline{U}L\ $ | $gU\overline{L}\ $ | $gUL\ $ | $nod$ | $|\\#|$ | $g\overline{U}R\ $ | $g\overline{U}L\ $ | $gU\overline{L}\ $ | $gUL\ $ | $nod$
20 | 5 | 5 | 37.0 | 0.0 | 0.0 | 0.0 | 1389 | 5 | 37.0 | 0.0 | 0.0 | 0.0 | 923 | 5 | 37.0 | 0.0 | 0.0 | 0.0 | 1 | 5 | 37.0 | 0.0 | 0.0 | 0.0 | 1
20 | 6 | 5 | 35.0 | 0.0 | 0.0 | 0.0 | 446 | 5 | 35.0 | 0.0 | 0.0 | 0.0 | 507 | 5 | 35.0 | 0.0 | 0.0 | 0.0 | 10 | 5 | 35.0 | 0.0 | 0.0 | 0.0 | 1
20 | 10 | 5 | 28.9 | 0.0 | 0.0 | 0.0 | 583 | 5 | 28.9 | 0.0 | 0.0 | 0.0 | 690 | 5 | 28.9 | 0.0 | 0.0 | 0.0 | 201 | 5 | 28.5 | 0.0 | 0.0 | 0.0 | 1
30 | 7 | 5 | 39.6 | 0.0 | 0.0 | 0.0 | 1072 | 5 | 39.6 | 0.0 | 0.0 | 0.0 | 1848 | 5 | 39.6 | 0.0 | 0.0 | 0.0 | 186 | 5 | 39.6 | 0.0 | 0.0 | 0.0 | 1
30 | 10 | 5 | 33.1 | 0.0 | 0.0 | 0.0 | 1429 | 5 | 33.1 | 0.0 | 0.0 | 0.0 | 1738 | 5 | 33.1 | 0.0 | 0.0 | 0.0 | 1 | 5 | 33.1 | 0.0 | 0.0 | 0.0 | 1
30 | 15 | 5 | 32.9 | 0.0 | 0.0 | 0.0 | 2352 | 5 | 33.0 | 0.0 | 0.0 | 0.0 | 2259 | 5 | 32.9 | 0.0 | 0.0 | 0.0 | 741 | 5 | 32.6 | 0.0 | 0.0 | 0.0 | 1
40 | 10 | 5 | 33.3 | 0.0 | 0.0 | 0.0 | 1870 | 4 | 33.3 | 1.8 | 1.1 | 2.9 | 891 | 5 | 33.3 | 0.0 | 0.0 | 0.0 | 1307 | 5 | 33.3 | 0.0 | 0.0 | 0.0 | 312
40 | 13 | 5 | 35.4 | 0.0 | 0.0 | 0.0 | 3157 | 4 | 35.4 | 0.8 | 0.0 | 0.8 | 7936 | 5 | 35.4 | 0.0 | 0.0 | 0.0 | 2313 | 5 | 35.4 | 0.0 | 0.0 | 0.0 | 1
40 | 20 | 5 | 28.6 | 0.0 | 0.0 | 0.0 | 3248 | 5 | 28.6 | 0.0 | 0.0 | 0.0 | 1638 | 5 | 28.6 | 0.0 | 0.0 | 0.0 | 2408 | 5 | 28.6 | 0.0 | 0.0 | 0.0 | 1
50 | 12 | 0 | 35.8 | 3.8 | 25.1 | 27.7 | 2100 | 0 | 35.8 | 2.8 | 30.3 | 32.3 | 1122 | 5 | 35.8 | 0.0 | 0.0 | 0.0 | 1248 | 5 | 35.8 | 0.0 | 0.0 | 0.0 | 685
50 | 16 | 1 | 35.7 | 1.7 | 1.8 | 3.5 | 1818 | 2 | 35.7 | 0.5 | 6.8 | 7.3 | 1928 | 5 | 35.7 | 0.0 | 0.0 | 0.0 | 1861 | 5 | 35.7 | 0.0 | 0.0 | 0.0 | 1
50 | 25 | 5 | 28.6 | 0.0 | 0.0 | 0.0 | 3730 | 4 | 28.6 | 0.6 | 0.0 | 0.6 | 7746 | 5 | 28.6 | 0.0 | 0.0 | 0.0 | 761 | 5 | 28.5 | 0.0 | 0.0 | 0.0 | 1
60 | 15 | 0 | 40.9 | 6.0 | 40.6 | 44.1 | 60 | 0 | 40.9 | 4.3 | 31.4 | 34.4 | 39 | 5 | 40.9 | 0.0 | 0.0 | 0.0 | 1571 | 5 | 40.9 | 0.0 | 0.0 | 0.0 | 16
60 | 20 | 0 | 35.5 | 4.5 | 24.9 | 28.2 | 592 | 0 | 35.5 | 3.1 | 22.4 | 24.6 | 126 | 5 | 35.5 | 0.0 | 0.0 | 0.0 | 4050 | 5 | 35.5 | 0.0 | 0.0 | 0.0 | 20
60 | 30 | 1 | 33.1 | 1.8 | 0.7 | 2.6 | 5686 | 1 | 33.1 | 1.4 | 1.4 | 2.7 | 4322 | 5 | 33.1 | 0.0 | 0.0 | 0.0 | 6466 | 5 | 32.8 | 0.0 | 0.0 | 0.0 | 1
70 | 17 | 0 | 37.5 | 8.7 | 58.1 | 61.8 | 14 | 0 | 37.5 | 8.6 | 62.5 | 65.7 | 2 | 4 | 37.5 | 0.6 | 0.0 | 0.6 | 2403 | 5 | 37.5 | 0.0 | 0.0 | 0.0 | 25
70 | 23 | 0 | 37.1 | 3.7 | 31.2 | 33.6 | 46 | 1 | 37.1 | 3.7 | 24.7 | 27.2 | 125 | 4 | 37.1 | 0.3 | 0.0 | 0.3 | 3503 | 5 | 37.1 | 0.0 | 0.0 | 0.0 | 1
70 | 35 | 2 | 30.8 | 0.7 | 4.7 | 5.4 | 1224 | 0 | 30.8 | 1.6 | 14.5 | 15.8 | 477 | 3 | 30.8 | 1.2 | 0.0 | 1.2 | 9547 | 5 | 30.7 | 0.0 | 0.0 | 0.0 | 1
80 | 20 | 0 | 39.3 | 11.6 | 61.1 | 65.6 | 3 | 0 | 39.3 | 10.4 | 59.6 | 63.9 | 1 | 1 | 39.3 | 2.6 | 2.2 | 4.7 | 3284 | 5 | 39.3 | 0.0 | 0.0 | 0.0 | 607
80 | 26 | 0 | 37.0 | 6.0 | 43.5 | 46.9 | 13 | 0 | 37.0 | 4.6 | 39.3 | 42.0 | 4 | 3 | 37.0 | 1.7 | 0.3 | 2.0 | 2327 | 5 | 37.0 | 0.0 | 0.0 | 0.0 | 1
80 | 40 | 0 | 31.2 | 3.6 | 19.0 | 21.8 | 740 | 1 | 31.2 | 1.9 | 20.6 | 21.9 | 511 | 3 | 31.2 | 1.0 | 0.0 | 1.0 | 12871 | 5 | 31.0 | 0.0 | 0.0 | 0.0 | 1
90 | 22 | 0 | 41.7 | 14.5 | 59.9 | 64.3 | 1 | 0 | 41.7 | 12.9 | 63.1 | 66.6 | 1 | 2 | 41.7 | 5.9 | 5.4 | 7.5 | 1930 | 4 | 41.7 | 3.7 | 9.4 | 9.4 | 456
90 | 30 | 0 | 38.4 | 6.4 | 47.3 | 50.9 | 1 | 0 | 38.4 | 4.7 | 47.6 | 50.1 | 1 | 2 | 38.4 | 1.6 | 0.4 | 2.0 | 4826 | 5 | 38.4 | 0.0 | 0.0 | 0.0 | 1
90 | 45 | 0 | 29.3 | 2.6 | 32.4 | 34.2 | 2 | 0 | 29.3 | 1.1 | 28.8 | 29.5 | 60 | 3 | 29.3 | 0.4 | 0.2 | 0.6 | 18184 | 5 | 29.3 | 0.0 | 0.0 | 0.0 | 1
100 | 25 | 0 | 39.4 | 12.9 | 66.5 | 69.2 | 1 | 0 | 39.4 | 11.6 | 57.7 | 60.7 | 1 | 0 | 39.4 | 7.8 | 5.9 | 8.5 | 1241 | 1 | 39.4 | 5.7 | 30.0 | 30.2 | 1
100 | 33 | 0 | 35.4 | 6.6 | 58.5 | 61.2 | 1 | 0 | 35.4 | 5.2 | 50.5 | 52.9 | 1 | 0 | 35.4 | 2.7 | 0.7 | 3.2 | 861 | 4 | 35.4 | 0.2 | 0.7 | 0.7 | 1
100 | 50 | 0 | 29.7 | 1.9 | 17.9 | 19.5 | 1 | 0 | 29.7 | 1.4 | 39.4 | 40.3 | 1 | 2 | 29.7 | 2.2 | 0.0 | 2.2 | 10014 | 5 | 29.7 | 0.0 | 0.0 | 0.0 | 1

Table 6: OMT summary results for median criterion

| $F1_{x^{\ell}}^{mtz}$ | $F1_{x^{\ell}}^{flow1}$ | $F1_{u}^{mtz}$ | $F1_{u}^{km}$
---|---|---|---|---
$|V|$ | $p$ | $|\\#|$ | $g\overline{U}R\ $ | $g\overline{U}L\ $ | $gU\overline{L}\ $ | $gUL\ $ | $nod$ | $|\\#|$ | $g\overline{U}R\ $ | $g\overline{U}L\ $ | $gU\overline{L}\ $ | $gUL\ $ | $nod$ | $|\\#|$ | $g\overline{U}R\ $ | $g\overline{U}L\ $ | $gU\overline{L}\ $ | $gUL\ $ | $nod$ | $|\\#|$ | $g\overline{U}R\ $ | $g\overline{U}L\ $ | $gU\overline{L}\ $ | $gUL\ $ | $nod$
20 | 5 | 5 | 62.7 | 0.0 | 0.0 | 0.0 | 96364 | 5 | 62.7 | 0.0 | 0.0 | 0.0 | 47977 | 5 | 62.7 | 0.0 | 0.0 | 0.0 | 3417 | 5 | 62.7 | 0.0 | 0.0 | 0.0 | 715
20 | 6 | 3 | 65.0 | 4.7 | 0.0 | 4.7 | 357899 | 5 | 65.0 | 0.1 | 0.1 | 0.0 | 209755 | 5 | 65.0 | 0.0 | 0.0 | 0.0 | 3481 | 5 | 65.0 | 0.0 | 0.0 | 0.0 | 1014
20 | 10 | 4 | 56.8 | 4.3 | 2.3 | 2.3 | 261456 | 5 | 56.8 | 2.6 | 2.3 | 0.0 | 183729 | 5 | 56.8 | 0.0 | 0.0 | 0.0 | 1164 | 5 | 56.8 | 0.0 | 0.0 | 0.0 | 1
30 | 7 | 0 | 65.5 | 29.7 | 0.6 | 30.2 | 44504 | 0 | 65.5 | 29.6 | 0.4 | 29.9 | 37888 | 5 | 65.5 | 0.0 | 0.0 | 0.0 | 7488 | 5 | 65.5 | 0.0 | 0.0 | 0.0 | 4011
30 | 10 | 1 | 61.2 | 19.4 | 0.0 | 19.4 | 47592 | 0 | 61.2 | 23.3 | 0.0 | 23.3 | 36047 | 5 | 61.2 | 0.0 | 0.0 | 0.0 | 7779 | 5 | 61.2 | 0.0 | 0.0 | 0.0 | 2103
30 | 15 | 0 | 59.9 | 19.4 | 0.0 | 19.4 | 58970 | 0 | 59.9 | 15.2 | 0.3 | 15.5 | 58878 | 5 | 59.9 | 0.0 | 0.0 | 0.0 | 4567 | 5 | 59.9 | 0.0 | 0.0 | 0.0 | 623
40 | 10 | 0 | 63.8 | 38.7 | 7.3 | 43.2 | 7036 | 0 | 63.8 | 39.2 | 12.0 | 46.1 | 4635 | 4 | 63.8 | 1.4 | 0.0 | 1.4 | 32844 | 5 | 63.8 | 0.0 | 0.0 | 0.0 | 13081
40 | 13 | 0 | 61.0 | 33.7 | 6.3 | 37.9 | 8680 | 0 | 61.0 | 32.6 | 4.0 | 35.3 | 5603 | 5 | 61.0 | 0.0 | 0.0 | 0.0 | 19517 | 5 | 61.0 | 0.0 | 0.0 | 0.0 | 4850
40 | 20 | 0 | 59.0 | 29.4 | 0.9 | 30.0 | 22945 | 0 | 59.0 | 26.5 | 0.8 | 27.1 | 22201 | 4 | 59.0 | 1.1 | 0.0 | 1.1 | 18341 | 5 | 59.0 | 0.0 | 0.0 | 0.0 | 3828
50 | 12 | 0 | 63.6 | 42.9 | 22.5 | 54.6 | 3221 | 0 | 63.6 | 43.7 | 22.4 | 55.3 | 2392 | 1 | 63.6 | 5.6 | 2.8 | 5.6 | 29239 | 2 | 63.6 | 3.6 | 2.9 | 3.7 | 16817
50 | 16 | 0 | 63.5 | 38.8 | 24.2 | 53.6 | 5640 | 0 | 63.5 | 40.6 | 15.8 | 49.9 | 3803 | 3 | 63.5 | 1.0 | 0.0 | 1.0 | 28974 | 5 | 63.5 | 0.0 | 0.0 | 0.0 | 7460
50 | 25 | 0 | 56.7 | 29.4 | 2.7 | 31.3 | 6883 | 0 | 56.7 | 29.7 | 1.4 | 30.7 | 5275 | 5 | 56.7 | 0.0 | 0.0 | 0.0 | 11380 | 5 | 56.7 | 0.0 | 0.0 | 0.0 | 3227
60 | 15 | 0 | 67.4 | 47.9 | 31.9 | 62.2 | 114 | 0 | 67.4 | 47.0 | 32.4 | 61.7 | 97 | 3 | 67.4 | 2.1 | 6.3 | 2.2 | 24493 | 0 | 67.4 | 13.3 | 6.2 | 13.4 | 5031
60 | 20 | 0 | 61.7 | 43.4 | 17.9 | 52.9 | 2079 | 0 | 61.7 | 42.0 | 18.9 | 52.5 | 1745 | 3 | 61.7 | 1.2 | 1.1 | 1.2 | 28959 | 2 | 61.7 | 6.4 | 1.1 | 6.4 | 4690
60 | 30 | 0 | 60.9 | 37.1 | 6.3 | 40.8 | 5730 | 0 | 60.9 | 37.1 | 5.3 | 40.2 | 4108 | 3 | 60.9 | 0.7 | 0.3 | 0.7 | 36946 | 5 | 60.9 | 0.0 | 0.3 | 0.0 | 5250
70 | 17 | 0 | 63.9 | 46.6 | 49.0 | 69.2 | 24 | 0 | 63.9 | 47.1 | 51.6 | 71.0 | 15 | 0 | 63.9 | 12.3 | 12.2 | 12.6 | 7941 | 0 | 63.9 | 18.2 | 11.8 | 18.1 | 1629
70 | 23 | 0 | 62.7 | 42.7 | 22.7 | 55.2 | 221 | 0 | 62.7 | 41.8 | 24.8 | 55.9 | 22 | 2 | 62.7 | 4.8 | 1.5 | 5.2 | 7571 | 0 | 62.7 | 11.6 | 1.7 | 12.1 | 1859
70 | 35 | 0 | 59.9 | 42.3 | 8.8 | 47.3 | 1149 | 0 | 59.9 | 41.7 | 7.9 | 46.3 | 285 | 1 | 59.9 | 2.9 | 0.0 | 2.9 | 24419 | 2 | 59.9 | 4.5 | 0.0 | 4.5 | 3371
80 | 20 | 0 | 65.7 | 49.8 | 55.2 | 72.2 | 10 | 0 | 65.7 | 49.2 | 55.3 | 71.9 | 2 | 0 | 65.7 | 22.3 | 27.2 | 29.9 | 4682 | 0 | 65.7 | 21.2 | 19.7 | 21.8 | 44
80 | 26 | 0 | 64.8 | 47.1 | 35.0 | 62.6 | 6 | 0 | 64.8 | 46.3 | 32.9 | 60.7 | 3 | 0 | 64.8 | 14.6 | 8.8 | 15.2 | 3180 | 0 | 64.8 | 17.0 | 14.0 | 22.3 | 14
80 | 40 | 0 | 60.3 | 42.0 | 16.8 | 51.5 | 44 | 0 | 60.3 | 42.1 | 18.7 | 52.9 | 16 | 1 | 60.3 | 2.7 | 0.0 | 2.7 | 13274 | 0 | 60.3 | 6.5 | 0.0 | 6.5 | 2172
90 | 22 | 0 | 66.1 | 50.2 | 51.4 | 69.9 | 3 | 0 | 66.1 | 49.0 | 52.4 | 69.9 | 1 | 0 | 66.1 | 19.7 | 20.0 | 20.4 | 3377 | 0 | 66.1 | 21.2 | 22.0 | 23.7 | 445
90 | 30 | 0 | 64.4 | 44.4 | 31.8 | 59.1 | 15 | 0 | 64.4 | 44.2 | 28.7 | 57.0 | 5 | 0 | 64.4 | 10.3 | 7.4 | 10.5 | 4525 | 0 | 64.4 | 14.6 | 8.1 | 15.4 | 21
90 | 45 | 0 | 58.3 | 41.7 | 19.4 | 53.1 | 62 | 0 | 58.3 | 39.9 | 17.5 | 50.4 | 6 | 1 | 58.3 | 1.9 | 0.0 | 1.9 | 14687 | 0 | 58.3 | 9.4 | 0.3 | 9.7 | 502
100 | 25 | 0 | 65.4 | 50.2 | 53.8 | 70.3 | 1 | 0 | 65.4 | 49.2 | 54.4 | 70.1 | 1 | 0 | 65.4 | 24.4 | 27.4 | 29.2 | 2126 | 0 | 65.4 | 24.0 | 46.1 | 47.1 | 3
100 | 33 | 0 | 63.0 | 46.1 | 47.6 | 65.7 | 1 | 0 | 63.0 | 45.6 | 44.5 | 63.2 | 1 | 0 | 63.0 | 18.1 | 17.9 | 18.3 | 2024 | 0 | 63.0 | 17.9 | 22.7 | 22.9 | 1
100 | 50 | 0 | 59.4 | 44.0 | 34.7 | 59.9 | 1 | 0 | 59.4 | 43.2 | 29.3 | 55.8 | 1 | 0 | 59.4 | 8.8 | 8.8 | 8.8 | 2973 | 0 | 59.4 | 14.8 | 16.7 | 22.0 | 1

Table 7: OMT results summary for $k$-centrum criterion

| $F1_{x^{\ell}}^{mtz}$ | $F1_{x^{\ell}}^{flow1}$ | $F1_{u}^{mtz}$ | $F1_{u}^{km}$
---|---|---|---|---
$|V|$ | $p$ | $|\\#|$ | $g\overline{U}R\ $ | $g\overline{U}L\ $ | $gU\overline{L}\ $ | $gUL\ $ | $nod$ | $|\\#|$ | $g\overline{U}R\ $ | $g\overline{U}L\ $ | $gU\overline{L}\ $ | $gUL\ $ | $nod$ | $|\\#|$ | $g\overline{U}R\ $ | $g\overline{U}L\ $ | $gU\overline{L}\ $ | $gUL\ $ | $nod$ | $|\\#|$ | $g\overline{U}R\ $ | $g\overline{U}L\ $ | $gU\overline{L}\ $ | $gUL\ $ | $nod$
20 | 5 | 5 | 50.7 | 0.0 | 0.0 | 0.0 | 4523 | 5 | 50.7 | 1.4 | 1.3 | 0.0 | 3115 | 5 | 50.7 | 0.0 | 0.0 | 0.0 | 380 | 5 | 50.7 | 0.0 | 0.0 | 0.0 | 1
20 | 6 | 5 | 55.2 | 0.0 | 0.0 | 0.0 | 4310 | 5 | 55.2 | 0.0 | 0.0 | 0.0 | 3621 | 5 | 55.2 | 0.0 | 0.0 | 0.0 | 1 | 5 | 55.2 | 0.0 | 0.0 | 0.0 | 1
20 | 10 | 5 | 30.2 | 0.0 | 0.0 | 0.0 | 2783 | 5 | 30.2 | 0.0 | 0.0 | 0.0 | 1431 | 5 | 30.2 | 0.0 | 0.0 | 0.0 | 47 | 5 | 30.2 | 0.0 | 0.0 | 0.0 | 1
30 | 7 | 3 | 63.8 | 5.5 | 0.9 | 6.2 | 52055 | 2 | 63.8 | 8.0 | 0.2 | 8.2 | 53114 | 5 | 63.8 | 0.0 | 0.0 | 0.0 | 2193 | 5 | 63.8 | 0.0 | 0.0 | 0.0 | 124
30 | 10 | 4 | 52.7 | 2.1 | 0.0 | 2.1 | 57428 | 4 | 52.7 | 1.5 | 0.0 | 1.5 | 57296 | 5 | 52.7 | 0.0 | 0.0 | 0.0 | 94 | 5 | 52.7 | 0.0 | 0.0 | 0.0 | 1
30 | 15 | 5 | 36.5 | 0.0 | 0.0 | 0.0 | 25282 | 5 | 36.5 | 0.0 | 0.0 | 0.0 | 3327 | 5 | 36.5 | 0.0 | 0.0 | 0.0 | 785 | 5 | 36.5 | 0.0 | 0.0 | 0.0 | 1
40 | 10 | 0 | 62.2 | 24.8 | 1.0 | 25.5 | 13425 | 0 | 62.2 | 23.9 | 2.1 | 25.4 | 15005 | 5 | 62.2 | 0.0 | 0.0 | 0.0 | 3726 | 5 | 62.2 | 0.0 | 0.0 | 0.0 | 1109
40 | 13 | 0 | 53.9 | 20.3 | 2.9 | 22.6 | 19263 | 1 | 53.9 | 14.7 | 0.6 | 15.2 | 23252 | 5 | 53.9 | 0.0 | 0.0 | 0.0 | 1960 | 5 | 53.9 | 0.0 | 0.0 | 0.0 | 1
40 | 20 | 4 | 32.1 | 0.7 | 0.0 | 0.7 | 24221 | 5 | 32.1 | 0.0 | 0.0 | 0.0 | 7279 | 5 | 32.1 | 0.0 | 0.0 | 0.0 | 947 | 5 | 32.1 | 0.0 | 0.0 | 0.0 | 1
50 | 12 | 0 | 58.0 | 26.7 | 10.4 | 34.0 | 4126 | 0 | 58.0 | 27.6 | 10.5 | 35.1 | 4075 | 5 | 58.0 | 0.0 | 0.0 | 0.0 | 4467 | 5 | 58.0 | 0.0 | 0.0 | 0.0 | 2825
50 | 16 | 0 | 55.2 | 18.3 | 1.1 | 19.2 | 1647 | 0 | 55.2 | 19.0 | 3.3 | 21.7 | 3132 | 5 | 55.2 | 0.0 | 0.0 | 0.0 | 755 | 5 | 55.2 | 0.0 | 0.0 | 0.0 | 1
50 | 25 | 1 | 32.2 | 5.2 | 0.2 | 5.3 | 7994 | 1 | 32.2 | 4.3 | 0.3 | 4.5 | 17390 | 5 | 32.2 | 0.0 | 0.0 | 0.0 | 3203 | 5 | 32.2 | 0.0 | 0.0 | 0.0 | 1
60 | 15 | 0 | 65.5 | 33.8 | 48.2 | 65.8 | 3583 | 0 | 65.5 | 33.0 | 39.5 | 59.6 | 1338 | 5 | 65.5 | 0.0 | 0.0 | 0.0 | 5514 | 5 | 65.5 | 0.0 | 0.0 | 0.0 | 3910
60 | 20 | 0 | 53.2 | 22.0 | 15.9 | 34.4 | 1531 | 0 | 53.2 | 24.6 | 18.6 | 38.7 | 2728 | 1 | 53.2 | 1.6 | 0.4 | 2.0 | 486 | 5 | 53.2 | 0.0 | 0.0 | 0.0 | 1
60 | 30 | 0 | 32.7 | 9.3 | 0.2 | 9.4 | 2178 | 0 | 32.7 | 9.4 | 0.6 | 10.0 | 2325 | 5 | 32.7 | 0.0 | 0.0 | 0.0 | 2626 | 5 | 32.7 | 0.0 | 0.0 | 0.0 | 1
70 | 17 | 0 | 57.5 | 31.0 | 64.4 | 75.3 | 51 | 0 | 57.5 | 30.2 | 59.9 | 71.8 | 52 | 3 | 57.5 | 0.9 | 0.0 | 0.9 | 4735 | 2 | 57.5 | 1.3 | 0.0 | 1.3 | 5319
70 | 23 | 0 | 51.1 | 26.5 | 44.1 | 58.8 | 387 | 0 | 51.1 | 25.5 | 31.6 | 49.3 | 136 | 2 | 51.1 | 2.2 | 0.0 | 2.2 | 535 | 5 | 51.1 | 0.0 | 0.0 | 0.0 | 1
70 | 35 | 0 | 30.9 | 9.2 | 6.8 | 15.4 | 568 | 0 | 30.9 | 10.2 | 1.9 | 11.9 | 920 | 5 | 30.9 | 0.0 | 0.0 | 0.0 | 2683 | 5 | 30.9 | 0.0 | 0.0 | 0.0 | 1
80 | 20 | 0 | 60.4 | 28.9 | 71.0 | 79.4 | 27 | 0 | 60.4 | 28.4 | 70.9 | 78.9 | 18 | 0 | 60.4 | 6.2 | 11.8 | 7.6 | 1854 | 1 | 60.4 | 7.3 | 9.1 | 2.4 | 2759
80 | 26 | 0 | 50.3 | 22.5 | 67.3 | 75.7 | 32 | 0 | 50.3 | 22.1 | 66.7 | 74.4 | 19 | 3 | 50.3 | 12.9 | 11.9 | 1.9 | 556 | 4 | 50.3 | 13.5 | 12.1 | 0.3 | 13
80 | 40 | 0 | 32.8 | 13.3 | 34.1 | 33.1 | 94 | 0 | 32.8 | 13.7 | 30.2 | 38.3 | 42 | 3 | 32.8 | 13.8 | 15.6 | 0.3 | 2390 | 5 | 32.8 | 14.2 | 15.6 | 0.0 | 1
90 | 22 | 0 | 64.4 | 38.2 | 80.0 | 86.4 | 1 | 0 | 64.4 | 35.9 | 73.9 | 81.7 | 1 | 0 | 64.4 | 11.0 | 8.4 | 11.4 | 1794 | 0 | 64.4 | 8.3 | 18.6 | 18.7 | 11
90 | 30 | 0 | 53.2 | 28.5 | 69.5 | 78.2 | 9 | 0 | 53.2 | 28.6 | 64.7 | 74.6 | 6 | 2 | 53.2 | 1.6 | 0.6 | 1.9 | 41 | 4 | 53.2 | 0.3 | 0.3 | 0.3 | 1
90 | 45 | 0 | 32.2 | 14.1 | 36.8 | 45.8 | 24 | 0 | 32.2 | 14.2 | 51.6 | 58.4 | 2 | 0 | 32.2 | 1.9 | 0.0 | 1.9 | 1981 | 5 | 32.2 | 0.0 | 0.0 | 0.0 | 1
100 | 25 | 0 | 62.8 | 37.3 | 75.8 | 83.2 | 1 | 0 | 62.8 | 37.0 | 71.0 | 79.7 | 1 | 0 | 62.8 | 12.2 | 20.6 | 22.5 | 38 | 0 | 62.8 | 10.6 | 24.6 | 25.2 | 4
100 | 33 | 0 | 53.8 | 28.7 | 78.5 | 84.5 | 1 | 0 | 53.8 | 27.8 | 71.3 | 79.1 | 1 | 0 | 53.8 | 3.2 | 1.4 | 3.2 | 77 | 4 | 53.8 | 1.4 | 1.4 | 1.4 | 5
100 | 50 | 0 | 30.1 | 14.7 | 60.3 | 66.2 | 2 | 0 | 30.1 | 13.8 | 59.3 | 65.0 | 1 | 1 | 30.1 | 1.1 | 0.0 | 1.1 | 658 | 4 | 30.1 | 0.1 | 0.2 | 0.2 | 261

Table 8: OMT results summary for $k$-trimmed mean criterion

##  Appendix Appendix A: Extended information about the OMT Benders
decomposition

Our mathematical formulation can be solved using a Benders decomposition
framework (see Benders, 1962) that we briefly described in this section.

###  A.1 Classical Benders decomposition

In the classical Benders decomposition algorithm, the original mixed integer
problem is divided into two problems, a master problem (MP) and a subproblem
(SP), that are solved iteratively. The two problems are related, so the
outcome of one directly modifies the outcome of the other. First, the MP is
solved to obtain the values of certain fixed variables; with these, we can
then solve the SP. Once the SP has been solved, either new feasibility or new
optimality cuts are introduced within the MP until the lower and upper bounds
coincide. For the OMT, it arises to use DOMP as MP and MST as SP. For
instance, we can illustrate the MP via $F1_{x^{\ell}}^{\mathcal{T}}$ as
follows:

$\displaystyle\hskip
28.45274ptF^{MP}:\min\quad\frac{1}{\displaystyle{\sum_{\ell\in
V}\lambda_{\ell}}}\sum_{\ell\in V}\sum_{(i,j)\in
A}\lambda_{\ell}c_{ij}x_{ij}^{\ell}+\mu$ (26a)
$\displaystyle\textrm{s.t.:}\hskip 7.11317pt\sum_{i\in V}x_{ii}=p$ (26b)
$\displaystyle\hskip 34.99677pt\sum_{j\in V}x_{ij}=1$ $\displaystyle i\in V$
(26c) $\displaystyle\hskip 34.99677ptx_{ij}\leq x_{jj}$ $\displaystyle(i,j)\in
A:i\neq j$ (26d) $\displaystyle\hskip 34.99677ptx_{ij}=\sum_{\ell\in
V}x_{ij}^{\ell}$ $\displaystyle(i,j)\in A$ (26e) $\displaystyle\hskip
34.99677pt\sum_{(i,j)\in A}x_{ij}^{\ell}=1$ $\displaystyle\ell\in V$ (26f)
$\displaystyle\hskip 34.99677pt\sum_{(i,j)\in
A}c_{ij}x_{ij}^{\ell}\leq\sum_{(i,j)\in A}c_{ij}x_{ij}^{\ell+1}$
$\displaystyle\ell\in V:\ell<|V|$ (26g) $\displaystyle\hskip
34.99677ptx_{ij}\in\\{0,1\\}$ $\displaystyle(i,j)\in A$ (26h)
$\displaystyle\hskip 34.99677ptx_{ij}^{\ell}\in\\{0,1\\}$
$\displaystyle(i,j)\in A,\ell\in V$ (26i) $\displaystyle\hskip
34.99677pt\mu\geq 0.$ (26j)

Similar formulations of the MP can be introduced using other formulations
reviewed in Section 3.

A classical Benders decomposition framework is then illustrated in Algorithm
2. For this algorithm we keep the best upper and lower bounds found up to each
iteration, $UB$ and $LB$. The procedure is then as follows. The MP is solved
to optimality and both the objective function $obj^{MP}$, which can be split
into the sum of the OM objective ($obj^{OM}$) plus the $\mu$ term, and the
variables representing the facilities selected $\bar{x}=\\{x_{ii}\ |\
x_{ii}=1,\forall i\in V\\}$ are stored. At this moment, if possible, update
the lower bound using the MP objective. Thereafter, solve the MST subproblem
setting as facilities the previously $\bar{x}$ identified in the MP solution
and, if possible, update the upper bound using the (weighted) sum of the OM
plus the SP objectives, $obj^{OM}+obj^{SP}$. Finally, in any case, add the
optimality constraint $Opt.cut$ to the MP. This procedure is repeated until
the bounds are equalized.

1 $UB:=\infty$

2 $LB:=0$

3 while  _$UB\leq LB$_ do

4 Solve to optimality $F^{MP}\rightarrow(obj^{MP},\bar{x})$, where
$obj^{MP}=obj^{OM}+\mu$

5 if  _$obj^{MP} >LB$_ then

6 update LB

7 Solve to optimality $F^{SP}\rightarrow obj^{SP}$

8 if  _$obj^{OM}+obj^{SP} <UB$_ then

9 update UB

10 Add optimality constraint $Opt.cut$ to $F^{MP}$

Algorithm 2 OMT classical Benders decomposition

As aforementioned, the subproblem to deal with is the MST between the
facilities computed in the MP solution, which can be solved in polynomial time
using Kruskal algorithm. Once solved, the objective value of the subproblem
$obj^{SP}$ is used to build the following optimality constraint to add to the
MP:

$Opt.cut:\ \frac{obj^{SP}}{p-1}\Bigg{[}\sum_{i\in
V}\bar{x}_{ii}-(p-1)\Bigg{]}\leq\mu.$ (27)

For this $Opt.cut$, if the same $p$ facilities that have been selected as
inputs for the SP are selected in the MP, then the $\mu$ variable is increased
in the amount of the cost of the tree obtained as output in the SP. Otherwise,
if at least one different facility is selected, then $\mu$ does not change. In
other words, $\mu$ is null until the same $p$ facilities are selected again,
where $\mu$ turns strictly positive and the algorithm ends.

Note that in every iteration, only one $Opt.cut$ is added. For the general
Benders framework, some authors (e.g. see Fischetti et al., 2010) force the
addition of feasibility cuts even when the MP is feasible to boost the
algorithm. In our case, since our subproblem is always feasible, it is not
necessary to introduce feasibility cuts, but we can force a series of
suboptimal cuts to be introduced in each iteration after the optimal cut is
included.

Directly using $Opt.cut$ avoids having to go through the dual formulation of
our SP, as in most of the Benders decomposition frameworks. However, there
exists an implementation of the Kipp Martin ($km$) MST dual formulation in
Labbé et al. (2021) which can be use for this purpose. The $km$ MST
formulation and its dual form are adapted to the OMT structure as follows:

$\displaystyle\hskip 28.45274ptF^{km}:\min\sum_{(i,j)\in E}c_{ij}z_{ij}$ (28a)
$\displaystyle\hskip 34.99677ptz_{ij}\leq\bar{x}_{ii}$ $\displaystyle(i,j)\in
E$ (28b) $\displaystyle\hskip 34.99677ptz_{ij}\leq\bar{x}_{jj}$
$\displaystyle(i,j)\in E$ (28c) $\displaystyle\hskip 34.99677pt\sum_{(i,j)\in
E}z_{ij}=p-1$ (28d) $\displaystyle\hskip
34.99677pt\sum_{\begin{subarray}{c}(i^{\prime},j)\in E:\\\ (i^{\prime}=k\wedge
j=i)\\\ \lor\\\ (i^{\prime}=i\wedge
j=k)\end{subarray}}x_{i^{\prime}j}+\sum_{(i,j)\in A:j\neq k}q_{kij}\leq 1$
$\displaystyle k,i\in V:i\neq k$ (28e) $\displaystyle\hskip
34.99677ptq_{kij}+q_{kji}=z_{ij}$ $\displaystyle k\in V,(i,j)\in E:i,j\neq k$
(28f) $\displaystyle\hskip 34.99677ptz_{ij}\geq 0$ $\displaystyle(i,j)\in E$
(28g) $\displaystyle\hskip 34.99677ptq_{kij}\geq 0$ $\displaystyle k\in
V,(i,j)\in E.$ (28h)

$\displaystyle\hskip 28.45274ptF^{SP}:\max\alpha(p-1)-\sum_{k,i\in V:i\neq
k}\beta_{ki}-\sum_{(i,j)\in E}(\bar{x}_{ii}\tau_{ij}+\bar{x}_{jj}\eta_{ij})$
(29a) $\displaystyle\hskip 34.99677pt\alpha-\beta_{ij}-\beta_{ji}-\sum_{k\in
V:k\neq i,j}\gamma^{k}_{ij}-\tau_{ij}-\eta_{ij}\leq c_{ij}$
$\displaystyle(i,j)\in E$ (29b) $\displaystyle\hskip
34.99677pt-\beta_{ki}+\sum_{\begin{subarray}{c}(i^{\prime},j^{\prime})\in
E:\\\ (i^{\prime}=i\wedge j^{\prime}=j)\\\ \lor\\\ (i^{\prime}=j\wedge
j^{\prime}=i)\end{subarray}}\gamma^{k}_{i^{\prime}j^{\prime}}\leq 0$
$\displaystyle k\in V,(i,j)\in E:i,j\neq k$ (29c) $\displaystyle\hskip
34.99677pt\alpha\in\mathbb{R}$ (29d) $\displaystyle\hskip
34.99677pt\beta_{ki}\geq 0$ $\displaystyle k,i\in V:i\neq k$ (29e)
$\displaystyle\hskip 34.99677pt\gamma^{k}_{ij}\in\mathbb{R}$ $\displaystyle
k\in V,(i,j)\in E:i,j\neq k$ (29f) $\displaystyle\hskip
34.99677pt\tau_{ij}\geq 0$ $\displaystyle(i,j)\in E$ (29g)
$\displaystyle\hskip 34.99677pt\eta_{ij}\geq 0$ $\displaystyle(i,j)\in E.$
(29h)

Observe that, constraints (2e) are presented as disaggregated constraints
(28b)-(28c) in the SP because, although it has been computationally proven to
report worse results, dealing with continuous $z$ variables force to use the
disaggregated formulation. In this way, a different $Opt.cut$ can be
introduced using $F^{SD}$:

$Opt.cut:\ \frac{1}{p-1}\Big{[}\bar{\alpha}(p-1)-\sum_{k,i\in V:i\neq
k}\bar{\beta}_{ku}-\sum_{(i,j)\in
E}(x_{ii}\bar{\tau}_{ij}+x_{jj}\bar{\eta}_{ij})\Big{]}\leq\mu.$ (30)

###  A.2 Modern Benders decomposition

The classical Benders decomposition can be introduced into a branch-and-cut
framework (also known as branch-and-Benders-cut) for a more efficient approach
as illustrated in Algorithm 3. In this algorithm we initialize the
ramification tree $\mathfrak{T}$, considering solving the MP at the root node,
and an empty pool of cuts $\mathcal{P}$. Once solved the MP at the root node,
we start the branching procedure. If at a particular node of the ramification
process the solution found is fractional, keep branching. Otherwise, when an
integer solution is found, the lower bound is updated using the MP objective
value of the current ramification node $o^{\prime}\in\mathfrak{T}$, the SP is
solved fixing the facilities $\bar{x}$ obtained in the MP solution, the upper
bound is updated if possible and the optimality constraint $Opt.cut$ is added
to a pool $\mathcal{P}$ of cuts. The cuts from pool $\mathcal{P}$ are then
included for the MP solution in other nodes of $\mathfrak{T}$.

1 Set tree $\mathfrak{T}=\\{o\\}$, where $o=F^{MP}$ has no branching
constraints

2 Initialize a pool of cuts $\mathcal{P}=\emptyset$

3 while  _$\mathfrak{T}$ is nonempty_ do

4 Select a node $o^{\prime}\in\mathfrak{T}$

5 $\mathfrak{T}:=\mathfrak{T}\,\backslash\\{o^{\prime}\\}$

6 Solve $o^{\prime}$ considering $\mathcal{P}$ $\rightarrow\bar{x}$

7 if  _$\bar{x}$ is fractional_ then

8 Branch, resulting in nodes $o^{\prime\prime}$ and $o^{\prime\prime\prime}$

9
$\mathfrak{T}:=\mathfrak{T}\cup\\{o^{\prime\prime},o^{\prime\prime\prime}\\}$

10 else

11 Solve $F^{SD}\rightarrow(\bar{\alpha},\bar{\beta},\bar{\tau},\bar{\eta})$

12 Add optimality constraint $Opt.cut$ to $\mathcal{P}$

13 $\mathfrak{T}:=\mathfrak{T}\cup\\{o^{\prime}\\}$

14

15

16

Algorithm 3 OMT branch-and-Benders-cut

Embedding Benders cuts in a branch-and-cut framework allows to use different
strategies for producing these cuts. For instance, the cuts can be generated
in every feasible node, only in those nodes that have improved the lower bound
beyond a predefined threshold or only when incumbent solutions are found along
the search process. If caution is not taken, too many unnecessary cuts can be
produced slowing down the obtainment of master problem solution instead of
speeding it up.

###  A.3 Warm-start phase

In the classical Benders decomposition, every $Opt.cut$ added implies solving
to optimality a MP, which is computationally costly. In the modern approach,
the pool of cuts $\mathcal{P}$ considered in a specific node of the branch-
and-cut procedure may contain cuts that have already been identified, slowing
down the algorithm efficiency since it would reintroduce repeated cuts when
branching at different levels of $\mathfrak{T}$. For these reasons, it could
be helpful to consider a strategy to initialize the pool of cuts $\mathcal{P}$
prior to starting the procedures using a so called warm-start phase (e.g. see
Martins de Sa et al., 2013).

This warm-start phase can be introduced in both classical and modern
approaches. For the modern approach, the idea is to store the cuts generated
in an independent warm-start phase in the pool of cuts $\mathcal{P}$ settled
at the beginning of Algorithm 3. Given $\textsf{runtime}^{MP}$, elapsed time
for a MP iteration, and runtime, total elapsed time for the completition of
the algorithm, the parameters considered for tuning the warm-start phase are
the following:

  * •

$\textsf{max.time}^{MP}$. Time limit that every solution computation of the MP
in the warm-start phase can take to obtain the best feasible solution
possible. Once reached, the respective $Opt.cut$ is added and a new MP is
considered for solving.

  * •

$\textsf{max.gap}^{MP}$. Gap percentage allowed to remain between the best
lower and upper bound found in every MP of the warm-start phase, $LB^{MP}$ and
$UB^{MP}$, computed as $100\cdot\frac{UB^{MP}-LB^{MP}}{LB^{MP}}$. Once
reached, the respective $Opt.cut$ is added and a new MP is considered for
solving.

  * •

max.time. Total time limit that the entire warm-start phase can take. Once
reached, the warm-start phase is finished and the algorithm starts searching
for optimal solutions.

  * •

max.gap. Gap percentage allowed to remain between best lower and upper bound
found in the entire warm-start phase, computed as in $\textsf{max.gap}^{MP}$
but using the overall bounds $LB$ and $UB$. Once reached, the warm-start phase
is finished and the algorithm starts searching for optimal solutions.

The interest behind this warm-star phase is to be able to introduce a certain
number of cuts at low cost in the beginning of the procedures avoiding, on
many occasions, that these cuts that have already been introduced are
considered again, improving the overall performance of the of the Benders
decomposition algorithms. In order to introduce this cuts, the solution in the
warm-start phase does not need to be computed to optimality, it is enough if
it is feasible. Furthermore, a procedure to build cuts from fractional values
of the variables can be implemented.

##  Appendix Appendix B: OMT covering fixing preprocessings example

Let consider the complete instance of the OMT with $|V|=4$ in Figure 5 (left)
and the allocation costs specified over its edges. We want to locate $p=2$
facilities considering a scaling vector of $\lambda=(1,\overset{N}{\ldots},1)$
(median criterion). Note that we assume that $c_{ii}=0$ for $i\in V$. The
optimal allocations (arrows) and facilities (squares) for this instance are
depicted in Figure 5 (right).

14232153241423212000000 Figure 5: OMT instance example (left) and its optimal
solution (right).

In the optimal solution we get a total allocation cost of 4, given by $c_{21}$
plus $c_{43}$ (also plus $c_{11}$ and $c_{33}$ that are zero). Facilities are
connected by means of $(1,3)$, holding itself the tree of facilities structure
expected in any solution of the OMT.

In order to illustrate how the covering formulation preprocessings for fixing
a certain number of $u_{\ell h}$-variables to 1 or 0 using the auxiliary
problems $F^{pre}_{1}$ and $F^{pre}_{0}$, we must first consider the ordered
sequence of unique costs
$c_{(0)}:=0<c_{(1)}<c_{(2)}<\ldots<c_{(|H|)}=\max_{i,j\in V}c_{ij}$ of our
problem as in Table 9.

$c_{(0)}$ | $c_{(1)}$ | $c_{(2)}$ | $c_{(3)}$ | $c_{(4)}$ | $c_{(5)}$
---|---|---|---|---|---
0 | 1 | 2 | 3 | 4 | 5
Table 9: Sequence of unique ordered costs for the OMT example.

Note that cost 0 is repeated 4 times, since we have 4 possible allocations of
facilities to themselves, and cost 2 is also repeated 2 times. For the
covering formulation, the $u$-matrix of dimensions $|V|\times|H|$ of the
optimal solution is given by the matrix

$u_{\ell h}=\begin{pmatrix}0&0&0&0&0\\\ 0&0&0&0&0\\\ 1&1&0&0&0\\\
1&1&0&0&0\end{pmatrix},$

which means that the $u_{\ell h}$ variables activated are
$u_{31},u_{32},u_{41},u_{42}=1$. Note that we are not considering the
$c_{(0)}$ column in the $u$-matrix, which in case of being considered must be
$u_{\ell 0}=1$ for $\ell\in V$. We can verify over this matrix that the
allocation cost objective holds using covering variables:

$\displaystyle\sum_{\ell\in V}\sum_{h\in H}\lambda_{\ell}u_{\ell
h}(c_{(h)}-c_{(h-1)})$
$\displaystyle=u_{31}(c_{(1)}-c_{(0)})+u_{32}(c_{(2)}-c_{(1)})+u_{41}(c_{(1)}-c_{(0)})+u_{42}(c_{(2)}-c_{(1)})=$
$\displaystyle=(1-0)+(2-1)+(1-0)+(2-1)=4.$

Now, if we want to previously fix a certain number of $u_{\ell h}$-variables
to 1, we deal with the auxiliary problem $F^{pre}_{1}$. In this problem we try
to maximize the number of allocations satisfying $c_{ij}\leq c_{(h-1)}$ from
which, given that there exists a total of $|V|$ possible allocations, we can
get the minimum number of allocations satisfying $c_{ij}>c_{(h-1)}\equiv
c_{ij}\geq c_{(h)}$, as specified in the covering formulation by constraints
3g. For example, if $h=1$, we are looking for allocations satisfying
$c_{ij}x_{ij}\leq c_{(0)}=0$. Only the 4 allocations at a cost 0 of the
potential facilities to themselves can be considered in this case, but because
constraints (24b) must be satisfied, only 2 of these allocations can be
selected and, therefore, the solution is $H_{1}^{1}=2$. This means that there
are at least $N-H_{1}^{1}=2$ allocations that satisfy the opposite and, as the
ones are placed in the lower part of the $u$-matrix, we have $u_{\ell 1}=1$
for any $\ell\in\\{N-H_{1}^{1}+1,\ldots,N\\}=\\{3,4\\}$. For $h=2$, we
consider again 2 of the 4 allocations of a facility to itself and only one
more allocation, which is $x_{13}$, and as a consequence we have
$H_{2}^{1}=3$. Hence, only $N-H_{2}^{1}=1$ variable can be fixed, which
corresponds to $u_{42}=1$. Following the same reasoning, we get $H^{1}_{h}=4$
for $h\geq 3$, so we are not able to fix any more variables.

On the other hand, for fixing $u_{\ell h}$-variables to 0 we deal with the
auxiliary problem $F^{pre}_{0}$. In our example, for $h=5$ we have only one
possible allocation that satisfies $c_{ij}\geq c_{(5)}x_{ij}=5x_{ij}$ plus the
2 allocations coming from constraints (25b). This means that as much
$H^{0}_{5}=3$ of the $u_{\ell 5}$-variables could be fixed to 1 (there could
be less), so the 5-th column of the $u$-matrix must have at least
$N-H^{0}_{5}=4-3=1$ zeros. However, as we know that the $p$ first rows of the
$u$-matrix can be fixed to 0, we end up having $u_{\ell 5}=0$ for any
$\ell\in\\{1,\ldots,N-H^{0}_{5}+p\\}=\\{1,2,3\\}$. For $h\leq 4$ the optimal
solution of the auxiliary problem is $H^{0}_{h}=4$ and consequently we are
only able to fix the $p$ first variables of each column that we knew in
advance.

We can summarize the previous information in the following table:

$h$ | $\overset{H_{h}^{1}}{\overbrace{\text{\\# alloc}|c_{ij}\leq c_{(h-1)}}}$ | $N-H_{h}^{1}$ | $\overset{H_{h}^{0}}{\overbrace{\text{\\# alloc}|c_{ij}\geq c_{(h-1)}}}$ | $N-H_{h}^{0}+p$
---|---|---|---|---
1 | 2 | 2 | 4 | 2
2 | 3 | 1 | 4 | 2
3 | 4 | 0 | 4 | 2
4 | 4 | 0 | 4 | 2
5 | 4 | 0 | 3 | 3
Table 10: Fixing solutions for the OMT example.

Thus, solving both auxiliary problems, we get the following final
preprocessing matrix of $u_{\ell h}$-variables fixed, where $NF$ means not
fixed by any of the auxiliary problems:

$preproc(u_{\ell h})=\begin{pmatrix}0&0&0&0&0\\\ 0&0&0&0&0\\\ 1&NF&NF&NF&0\\\
1&1&NF&NF&NF\end{pmatrix}.$

##  Appendix Appendix C: OMT formulations description

###  C.1 OMT subtour elimination formulation

$\displaystyle\hskip 28.45274ptF1_{x}^{sub1}:\min\quad\frac{1}{\sum_{\ell\in
V}\lambda_{\ell}}\sum_{\ell\in V}\sum_{i,j\in
V}\lambda_{\ell}c_{ij}x_{ij}^{\ell}+\frac{1}{p-1}\sum_{i,j\in
V:i<j}c_{ij}z_{ij}$ (31a) $\displaystyle\textrm{s.t.:}\hskip
7.11317pt\sum_{i\in V}x_{ii}=p$ (31b) $\displaystyle\hskip
34.99677pt\sum_{j\in V}x_{ij}=1$ $\displaystyle\forall i\in V$ (31c)
$\displaystyle\hskip 34.99677ptx_{ij}\leq x_{jj}$ $\displaystyle\forall i,j\in
V:i\neq j$ (31d) $\displaystyle\hskip 34.99677pt2z_{ij}\leq x_{ii}+x_{jj}$
$\displaystyle\forall i,j\in V:i<j$ (31e) $\displaystyle\hskip
34.99677pt\sum_{i,j\in V:i<j}z_{ij}=p-1$ (31f) $\displaystyle\hskip
34.99677pt\sum_{i,j\in S:i<j}z_{ij}\leq|S|-1$ $\displaystyle\forall
S\neq\emptyset,S\subset V$ (31g) $\displaystyle\hskip 34.99677pt\sum_{\ell\in
V}x_{ij}^{\ell}=x_{ij}$ $\displaystyle\forall i,j\in V$ (31h)
$\displaystyle\hskip 34.99677pt\sum_{i,j\in V}x_{ij}^{\ell}=1$
$\displaystyle\forall\ell\in V$ (31i) $\displaystyle\hskip
34.99677pt\sum_{i,j\in V}c_{ij}x_{ij}^{\ell}\leq\sum_{i,j\in
V}c_{ij}x_{ij}^{\ell+1}$ $\displaystyle\forall\ell\in V:\ell<|V|$ (31j)
$\displaystyle\hskip 34.99677ptx_{ij}\in\\{0,1\\}$ $\displaystyle\forall
i,j\in V$ (31k) $\displaystyle\hskip 34.99677ptz_{ij}\in\\{0,1\\}$
$\displaystyle\forall i,j\in V:i<j$ (31l) $\displaystyle\hskip
34.99677ptx_{ij}^{\ell}\in\\{0,1\\}$ $\displaystyle\forall i,j,\ell\in V.$
(31m)

  * (31a): Weighted minimization of the compensated allocation cost of the system plus the design cost of the tree connecting facilities (objective).

  * (31b): Exactly $p$ facilities (allocation).

  * (31c): Each client is allocated to exactly one facility (allocation).

  * (31d): No client is allocated to a non-facility (allocation).

  * (31e): Edges of the tree of facilities can only be selected if both nodes are facilities (allocation).

  * (31f): Exactly $p-1$ edges connecting facilities (connectivity).

  * (31g): No subtours are allowed to be formed between facilities edges (connectivity).

  * (31h): Relationship between sorting and allocation variables (sorting).

  * (31i): Every sort position must be consider (sorting).

  * (31j): Correct sorting of the costs sequence (sorting).

$\displaystyle\hskip 28.45274ptF1_{x}^{sub2}:\min\quad\frac{1}{\sum_{\ell\in
V}\lambda_{\ell}}\sum_{\ell\in V}\sum_{i,j\in
V}\lambda_{\ell}c_{ij}x_{ij}^{\ell}+\frac{1}{p-1}\sum_{i,j\in
V:i<j}c_{ij}z_{ij}$ (32a) $\displaystyle\textrm{s.t.:}\hskip
7.11317pt\sum_{i\in V}x_{ii}=p$ (32b) $\displaystyle\hskip
34.99677pt\sum_{j\in V}x_{ij}=1$ $\displaystyle\forall i\in V$ (32c)
$\displaystyle\hskip 34.99677ptx_{ij}\leq x_{jj}$ $\displaystyle\forall i,j\in
V:i\neq j$ (32d) $\displaystyle\hskip 34.99677pt2z_{ij}\leq x_{ii}+x_{jj}$
$\displaystyle\forall i,j\in V:i<j$ (32e) $\displaystyle\hskip
34.99677pt\sum_{i,j\in V:i<j}z_{ij}=p-1$ (32f) $\displaystyle\hskip
34.99677pt\displaystyle{\sum_{i\in S,j\in V\setminus
S}}x_{ij}+\displaystyle{\sum_{i\in S,j\in V\setminus
S}}x_{ji}+\displaystyle{\sum_{i\in S,j\in V\setminus
S:i<j}}z_{ij}+\displaystyle{\sum_{i\in S,j\in V\setminus S:i>j}}z_{ji}\geq 1$
$\displaystyle\forall S\neq\emptyset,S\subset V$ (32g) $\displaystyle\hskip
34.99677pt\sum_{\ell\in V}x_{ij}^{\ell}=x_{ij}$ $\displaystyle\forall i,j\in
V$ (32h) $\displaystyle\hskip 34.99677pt\sum_{i,j\in V}x_{ij}^{\ell}=1$
$\displaystyle\forall\ell\in V$ (32i) $\displaystyle\hskip
34.99677pt\sum_{i,j\in V}c_{ij}x_{ij}^{\ell}\leq\sum_{i,j\in
V}c_{ij}x_{ij}^{\ell+1}$ $\displaystyle\forall\ell\in V:\ell<|V|$ (32j)
$\displaystyle\hskip 34.99677ptx_{ij}\in\\{0,1\\}$ $\displaystyle\forall
i,j\in V$ (32k) $\displaystyle\hskip 34.99677ptz_{ij}\in\\{0,1\\}$
$\displaystyle\forall i,j\in V:i<j$ (32l) $\displaystyle\hskip
34.99677ptx_{ij}^{\ell}\in\\{0,1\\}$ $\displaystyle\forall i,j,\ell\in V.$
(32m)

  * (32a): Weighted minimization of the compensated allocation cost of the system plus the design cost of the tree connecting facilities (objective).

  * (32b): Exactly $p$ facilities (allocation).

  * (32c): Each client is allocated to exactly one facility (allocation).

  * (32d): No client is allocated to a non-facility (allocation).

  * (32e): Edges of the tree of facilities can only be selected if both nodes are facilities (allocation).

  * (32f): Exactly $p-1$ edges connecting facilities (connectivity).

  * (32g): At least one allocation or one edge from the tree of facilities must connect $S$ to a node of $V\setminus S$ (connectivity).

  * (32h): Relationship between sorting and allocation variables (sorting).

  * (32i): Every sort position must be consider (sorting).

  * (32j): Correct sorting of the costs sequence (sorting).

$\displaystyle\hskip
28.45274ptF2_{x}^{sub1}:\min\quad\frac{1}{\displaystyle{\sum_{\ell\in
V}\lambda_{\ell}}}\sum_{\ell\in V}\sum_{(i,j)\in
A}\lambda_{\ell}c_{ij}x_{ij}^{\ell}+\frac{1}{p-1}\sum_{(i,j)\in
E}c_{ij}(z_{ij}-x_{ij}-x_{ji})$ (33a) $\displaystyle\textrm{s.t.:}\hskip
7.11317pt\sum_{i\in V}x_{ii}=p$ (33b) $\displaystyle\hskip
34.99677pt\sum_{j\in V}x_{ij}=1$ $\displaystyle i\in V$ (33c)
$\displaystyle\hskip 34.99677pt2x_{ij}\leq 1-x_{ii}+x_{jj}$ $\displaystyle
i,j\in V:i\neq j$ (33d) $\displaystyle\hskip 34.99677ptx_{ij}+x_{ji}\leq
z_{ij}$ $\displaystyle i,j\in V:i<j$ (33e) $\displaystyle\hskip
34.99677pt2z_{ij}\leq x_{ii}+x_{jj}+x_{ij}+x_{ji}$ $\displaystyle i,j\in
V:i<j$ (33f) $\displaystyle\hskip 34.99677pt\sum_{i,j\in V:i<j}z_{ij}=N-1$
(33g) $\displaystyle\hskip 34.99677pt\sum_{i,j\in S:i<j}z_{ij}\leq|S|-1$
$\displaystyle\forall S\neq\emptyset,S\subset V$ (33h) $\displaystyle\hskip
34.99677ptx_{ij}=\sum_{\ell\in V}x_{ij}^{\ell}$ $\displaystyle\forall i,j\in
V:i\neq j$ (33i) $\displaystyle\hskip 34.99677pt\sum_{i,j\in
V}x_{ij}^{\ell}=1$ $\displaystyle\forall\ell\in V$ (33j) $\displaystyle\hskip
34.99677pt\sum_{i,j\in V}c_{ij}x_{ij}^{\ell}\leq\sum_{i,j\in
V}c_{ij}x_{ij}^{\ell+1}$ $\displaystyle\forall\ell\in V:\ell<|V|$ (33k)
$\displaystyle\hskip 34.99677ptx_{ij}\in\\{0,1\\}$ $\displaystyle\forall
i,j\in V$ (33l) $\displaystyle\hskip 34.99677ptz_{ij}\in\\{0,1\\}$
$\displaystyle\forall i,j\in V:i<j$ (33m) $\displaystyle\hskip
34.99677ptx_{ij}^{\ell}\in\\{0,1\\}$ $\displaystyle\forall i,j,\ell\in V.$
(33n)

  * (33a): Weighted minimization of the compensated allocation cost of the system plus the design cost of the tree subtracting in the design cost part the cost associated to the edges that represent the allocation of client to facilities (objective).

  * (33b): Exactly $p$ facilities (allocation).

  * (33c): Each client is allocated to exactly one facility (allocation).

  * (33d): Client-facility allocations are only possible if $i$ is a client and $j$ is a facility (allocation).

  * (33e): Only one allocation, whether client $i$ to facility $j$ or viceversa, can be considered if there exists an edge connecting $i,j\in V$ (allocation).

  * (33f): Only possibilities in which an edge can be selected is if both $i$ or $j$ are facilities or if either $i$, or $j$, is a client and $j$, or $i$ respectively, its facility (allocation).

  * (33g): Exactly $p-1$ edges connecting facilities (connectivity).

  * (33h): No subtours are allowed to be formed between facilities edges (connectivity).

  * (33i): Relationship between sorting and allocation variables (sorting).

  * (33j): Every sort position must be consider (sorting).

  * (33k): Correct sorting of the costs sequence (sorting).

The cardinality of the set of subtour elimination constraints is exponential
in the number of nodes. An effective algorithm can be implemented using a
branch-and-cut ramification process to add dynamically in polynomial time a
certain number of these constraints. Formulations $F2_{x}^{sub2}$,
$F1_{u}^{sub1}$, $F1_{u}^{sub2}$, $F2_{u}^{sub1}$ and $F2_{u}^{sub2}$ are left
to the reader.

###  C.2 OMT MTZ formulation

Let $D=(V,A,r)$ be a rooted weighted directed network where $A$ the set of
arcs and $r$ is a root node. An arborescence of $D$ is a subgraph