# Solving the Minimum Label Spanning Tree Problem by Mathematical Programming Techniques

Authors: Andreas M. Chwatal; Günther R. Raidl
Journal: Advances in Operations Research
 (2011)

---

## Abstract

We present exact mixed integer programming approaches including branch-and-cut and branch-and-cut-and-price for the minimum label spanning tree problem as well as a variant of it having multiple labels assigned to each edge. We compare formulations based on network flows and directed connectivity cuts. Further, we show how to use odd-hole inequalities and additional inequalities to strengthen the formulation. Label variables can be added dynamically to the model in the pricing step. Primal heuristics are incorporated into the framework to speed up the overall solution process. After a polyhedral comparison of the involved formulations, comprehensive computational experiments are presented in order to compare and evaluate the underlying formulations and the particular algorithmic building blocks of the overall branch-and-cut- (and-price) framework.


---

## Body

## 1. Introduction

The minimum label spanning tree (MLST) problem was first introduced in [1] and has, for instance, applications in telecommunication network design and data compression [2]. For the MLST problem we are given an undirected graph G=(V,E,l) with nodes (or vertices) v∈V and edges e∈E connecting pairs of nodes. In addition a labelling function l:E→L is given, assigning to each edge an element, called “label”, from a finite set L. The objective is to find a minimum cardinality label subset L′⊆L inducing a spanning tree in the sense that for each edge in the spanning tree, its corresponding label is selected. We also consider the situation of l:E→2L where more than one label can be assigned to an edge.


## 2. Related Work

The minimum label spanning tree (MLST) problem has been introduced by Chang and Leu [1] for the first time. In this work, the authors showed the MLST problem to be 𝒩𝒫-hard, and proposed an exact and an approximative algorithm called maximum vertex covering Algorithm (MVCA). Krumke and Wirth [3] proposed a modified construction algorithm and derived a performance guarantee for it. Moreover, it has been shown that the problem cannot be approximated with a constant factor. An improved performance bound has been obtained by Wan et al. [4], and a tight bound has then been found by Xiong et al. [5]. An experimental comparison of further MVCA variations is presented in [6].Besides approximative methods many metaheuristic algorithms have been proposed and studied in the literature during the last decade. Various genetic algorithms have been developed in [7, 8]. Methods based on local search have been treated from a theoretical point of view in [9], and from a more practical one in [10–14]. In particular, the latter publications also cover metaheuristics like greedy randomized search procedures, local search, variable neighborhood search and the pilot method.Less work does exist regarding exact algorithms. An exact algorithm based onA*-search has been proposed in [1], a similar approach, however, not using the guidance function of the A*-algorithm, has been proposed in [12]. So far, only two mathematical-programming approaches have been considered in the literature. The first mixed integer programming (MIP) formulation proposed by Chen et al. [15] is based on Miller-Tucker-Zemlin inequalities (cf. Section 3.1) which ensure that the decision variables for the edges induce a connected subgraph covering all nodes of the initial graph. In a recent work of Captivo et al. [16], the authors propose an MIP formulation based on single commodity flows, a frequently used modelling technique for spanning trees. A branch-and-cut algorithm based on directed connection cuts and cycle-elimination cuts for an extension of the MLST problem has been described in [17]. For a general introduction to integer linear programming-(ILP-) based algorithms like branch-and-cut and branch-and-price we refer the reader to [18].In this work we propose a branch-and-cut (and-price) (BCP) framework for the solution of moderately sized problem instances. We present a polyhedral and computational comparison of an underlying flow-formulation to a formulation based on directed connection cuts. The latter is proposed for this particular problem for the first time, and it is further shown how the cut-separation can be performed more efficiently than for many other spanning tree problems. New inequalities based on the label variables are introduced to strengthen the formulations. Optionally, also cycle-elimination cuts are separated. Furthermore we show how to use odd hole inequalities to strengthen the formulation by cutting off fractional values of the label variables. For these particular inequalities, a MIP-based separation heuristic is proposed for the first time. We further consider branch-and-cut-and-price, where instead of starting the algorithm with a full model, we start with a restricted set of labels and include further (label) variables only on demand. In order to obtain valid integral solutions in each node of the branch-and-bound (B&B) tree fast, we apply primal heuristics based on the well known MVCA-heuristic [3]. A detailed description of the formulations and algorithmic building blocks is given in Section 3, their properties are then theoretically investigated in Section 3.6. In Section 4, we finally present a comparison of the described formulations and algorithmic components based on computational experiments.


## 3. Mixed Integer Programming Framework

In this section we first give a rather abstract formulation of the MLST as mixed integer program (MIP). For the spanning-tree property, we present two concrete instantiations: (1) based on a flow-formulation, and (2) a formulation based on directed connectivity cuts, respectively. Both formulations as well as additional inequalities to strengthen the formulations and methods for cutting-plane separation and dynamic variable generation are described within one generic framework, as they can be used in different combinations.We use the following variables: variableszl∈{0,1}, for all l∈L indicate if label l is part of the solution; edge variables xe, for all e∈E, denote if edge e is used in the final spanning tree; variables yi,j, for all i,j∈V, denote directed arc variables used for the cut-based formulation, where we introduce for each edge e={i,j}∈E two arcs (i,j) and (j,i)∈A. For the flow formulation, we analogously introduce two directed flow variables fij,fji∈[0,n-1]. Let further L(e) denote the set of labels associated to edge e.


### 3.1. Mixed Integer Formulation

The basic formulation is given by the following abstract integer linear program:(3.1)min⁡.∑l∈Lzl,(3.2)s.t.∑l∈L(e)zl≥xe,∀e∈E,(3.3)x≡spanning tree,(3.4)zl∈{0,1}∀l∈L.The objective function (3.1) minimizes the number of required labels, Inequalities (3.2) ensure that for each selected edge (at least) one label is selected. For the abstract condition (3.3), we will subsequently introduce alternative formulations.The number of selected edges may be fixed according to a valid spanning tree:(3.5)∑e∈Exe=|V|-1.
Note, that (3.5) is however not required for a valid description of the MLST problem.


#### 3.1.1. Single-Commodity Flow Formulation

A single-commodity flow formulation, also considered in [16], is given as follows:(3.6)∑(0,i)∈Af0i=|V|-1,(3.7)∑(i,t)∈Afit-∑(t,j)∈Aftj=1∀t∈V∖{0},(3.8)fij≤(|V|-1)⋅xe∀{i,j}∈E,e={i,j}.Equation (3.6) ensures the correct quantity of flow leaving the (arbitrary) root node with index 0. For all other nodes flow consumption (3.7) must hold, that is, one unit of flow is consumed at each node. Inequalities (3.8) finally ensure that only edges with a sufficient amount of flow may be selected. Flow formulations have the big advantage that they permit to formulate a spanning tree by a polynomial number of variables and therefore provide a relatively compact model.


#### 3.1.2. Multicommodity Flow Formulation

The single-commodity flow formulation's major shortcoming is, however, that it provides a relatively poor LP-relaxation [19]. This is particularly due to the weak coupling of f to x-variables in Inequalities (3.8), the linking constraints. This drawback can be circumvented by the introduction of multiple commodities k for each node v∈V. Again, all flows of commodity k originate from node 0 and must be delivered to node k. The formulation is given by the following equalities:(3.9)∑(i,t)∈Afitk-∑(t,j)∈Aftjk={-1,t=0,0,t≠0∧t≠k,1,t=k.∀k∈V∖{0},
Linkage of flow to edge variables is then given by(3.10)xe≤fijk∀commoditiesk,∀e={i,j}∈E.This formulation, however, has the drawback of having more variables than the single-commodity flow formulation, that is,O(|V|·|E|) flow variables in contrast to only O(|E|).


#### 3.1.3. Directed Cut Formulation

An alternative formulation is given by directed-connection inequalities, stating that to each node a valid (directed) path must exist. In contrast to the flow model, this formulation consists of an exponential number of inequalities and therefore cannot be directly passed to an ILP-solver for larger instances. However, this formulation provides a better LP-relaxation to many spanning tree problems, as it exactly describes the convex hull of the minimum spanning tree polyhedron. The corresponding inequalities, linkage to the edge variables are given by the following:(3.11)∑(i,j)∈δ-(S)yij≥1∀S⊆V,0∉S,(3.12)xe≥yij∀{i,j}∈E,e={i,j}.Hereδ-(S) denotes the set of ingoing arcs to some node set S⊂V. Instead of Inequalities (3.12) we could also directly link the labels to the directed arcs. However, we proceed with Inequalities (3.12) for sake of a unified notation. The separation of these directed-connection inequalities is discussed in Section 3.2.It is well known to be practically advantageous to initially add the inequalities(3.13)yij+yji≤1,∀{i,j}∈E,(3.14)∑(i,j)∈δ-(j)yij≥1,∀j∈V∖{0},
to directed (cut-based) formulations, see [20, 21]. Inequalities (3.13) avoid short cycles corresponding to a single edge, Inequalities (3.14) assure that each node has one incoming arc. By δ-(i) we denote the set of incoming arcs to node i.


#### 3.1.4. Cycle-Elimination Formulation

We can also ensure feasibility for integer solutions bycycle-elimination inequalities. These inequalities enforce the resulting graph not to contain any cycles, which is together with the enforced number of arcs also a sufficient condition for spanning trees, and is given by the following Inequalities:(3.15)∑e∈Cxe≤|C|-1,∀cyclesC∈G,|C|>2.


#### 3.1.5. Miller-Tucker-Zemlin Formulation

A further way for prohibiting cycles is models based on the well-knownMiller-Tucker-Zemlin inequalities [22]. Such a model for the MLST problem has been proposed in [15], however with some differences. Let ui∈ℝ for all i∈V denote variables assigning numeric values to each node. By inequalities(3.16)ui-uj+|V|⋅yij≤|V|-1∀(i,j)∈A,(3.17)ui≤|V|∀i∈V,
cycles can be inhibited by just using a polynomial number of variables, however with the drawback, that a large multiplicative factor appears, usually leading to bad LP-relaxations. Main difference to the formulation proposed in [15] is the meaning of the variables. Whereas we use distinct variables for labels and edges (O(|E|+|L|) variables), and link them by Inequalities (3.8) which are in total O(|E|) constraints, they introduce O(|E|·|L|) variables xijk with i, j corresponding to edges {i,j} and index k corresponding to labels.In [16], the authors pointed out an important property of the flow formulation. They showed that the edge variables are not required to be an integer in order to obtain the correct (optimal) objective function value. Furthermore it is easy to derive a valid MLST solution based on the set of labels provided by the MIP solution. Based on this reasoning, we can establish the following theorem, which extends this result to further MLST formulations, and also immediately provides an improved cut formulation with a fast separation method.


#### 3.1.6. Epsilon-Connectivity Formulation

Theorem 3.1.
For any MIP formulation given by (3.1), (3.2) and (3.5), zl∈{0,1}, for all l∈L any set of labels corresponding to an optimal solution to this formulation, and additionally meeting the following inequalities “epsilon-connectivity”
(3.18)∑e∈δ(S)xe≥ϵ∀S⊂V,S≠∅
implies a valid MLST. Here, ϵ>0 denotes some arbitrary small real number.Proof.
The number of edges is fixed by (3.5), but a solution may still contain fractional edges. However, as the label variables z are integer and required to be greater than the value of the corresponding edge variables by Inequalities (3.2), they are always one if the corresponding edge variable has a value greater than ϵ. Consequently, fractional edge variables will only appear in the final solution if they do not raise the objective function value (by requiring additional labels). Due to Inequalities (3.18), the labels obtained from the MIP solution facilitate paths between all pairs of nodes.Given a label set of an optimal MIP solution, a feasible spanning tree can easily be derived in polynomial time, by determining an arbitrary spanning tree on the edges induced by the label set, as described in [16]. As a direct consequence of Theorem 3.1, the domain of the variables x and y need not be restricted to Boolean values, restricting them to nonnegative values by inequalities(3.19)xe≥0,∀e∈E,yi,j≥0,∀{i,j}∈E,yj,i≥0,∀{i,j}∈E,
is already sufficient.Theorem3.1 also suggests a further formulation for the MLST problem. Although not explicitly containing any constraints describing a valid spanning tree, (3.1), (3.2), (3.5), and (3.18) already provide a complete description to the MLST problem, and could be further strengthened by(3.20)∑e∈δ(i)xe≥1,∀i∈V,
and Inequalities (3.22), which are defined later on in Section 3.3. Inequalities (3.18) will again be separated on demand as cutting planes, which can, however, be performed more efficiently than the separation for the directed connection cuts, which will be discussed in detail in Section 3.2.Note that epsilon-connectivity as defined by Theorem3.1 is not guaranteed if cycle-elimination Inequalities (3.15) are used exclusively to describe a valid spanning tree. A fractional LP-solution not containing a cycle may still contain a subtour, that is, a subgraph where the sum over corresponding edges is larger than the size of its nodes minus one. Such a situation is depicted in Figure 1. As a consequence, the domain of the x-variables must be restricted to Boolean values if only cycle-elimination inequalities are used to describe a valid spanning tree. The same is true for the Miller-Tucker-Zemlin formulation given by Inequalities (3.16).Figure 1
LP-solution that does not contain a cycle w.r.t. Inequalities (3.15), but still violates subtour elimination constraints. Corresponding (integer) label solutions are not necessarily feasible.We now draw our attention to the special case of having only one single label assigned to each edge. If we have not fixed the number of edges, we can impose further equalities(3.21)∑l∈L(e)zl=xe,∀e∈E,
instead of Inequalities (3.2), which provide a more direct link between labels and their corresponding edges. This approach emphasizes the search for a feasible label set of minimal cardinality rather then the search for a feasible spanning tree.


### 3.2. Cutting-Plane Separation

The directed connection Inequalities (3.11) can be separated by computing the maximum flow from the root node r to each node i as target node. This provides a minimum (r,i)-cut. We have found a violated inequality if the value of the corresponding arcs according to the sum of the LP-values is less than 1. Our separation procedure utilizes Cherkassky and Goldberg's implementation of the push-relabel method for the maximum flow problem [23] to perform the required minimum cut computations.The cycle-elimination cuts (3.15) can be easily separated by shortest path computations with Dijkstra's algorithm. Hereby we use 1-yijLP as the arc weights with yijLP denoting the current value of the LP-relaxation for arc (i,j) in the current node of the B&B-tree. We obtain cycles by iteratively considering each arc (i,j)∈A and searching for the shortest path from j to i. If the value of a shortest path plus yijLP is less than 1, we have found a cycle violating Inequalities (3.15). We add this inequality to the LP and resolve it. In each node of the B&B-tree, we perform these cutting plane separations until no further cuts can be found.Theorem3.1 suggested a formulation not requiring any auxiliary variables (like flow or arc variables), where validity of the labels is obtained by Inequalities (3.18) exclusively. Instead of using the minimum cut-based separation routine (which would also be valid), we can perform a faster separation by a simple depth first search (DFS). Given an LP-solution, we first select an arbitrary start node for which we call the DFS procedure. Within this procedure we only consider edges e with xe≥ϵ. Within the DFS, we keep track of all visited nodes, if there are unvisited nodes at the end of the DFS, we have found a valid cut. The DFS can be carried out in O(|V|+|E|) time, which is clearly superior to the time of the maximum flow algorithm running in O(|V|·|E|+|V|2+ε).


### 3.3. Strengthening the Formulations

As each node must be connected to the spanning tree by one of its incident edges, we can further impose additional inequalities to strengthen the formulation w.r.t. the label variables:(3.22)∑l∈L(v)zl≥1,∀v∈V.
Here, L(v), v∈V denotes the set of labels being associated to the edges incident to node v. We will subsequently refer to this set of |V| inequalities as node-label-inequalities. Figure 2 gives a simple example of an LP solution where the node is sufficiently connected according to the sum of the LP-values of the ingoing arcs and therefore its incident edges, but the corresponding sum over the labels associated to these edges is clearly infeasible w.r.t. Inequalities (3.22). Therefore Inequalities (3.22) strengthen the presented formulations w.r.t. their LP-relaxation. In Section 3.6, we formally prove this property with respect to the particular proposed MIP-formulations for the MLST. Note, that we will use MIP variables and their corresponding graph-entities equivalently in the the context of subsequent figures and proofs for simplicity, for example, we will simply designate a label by a,b,… (or la,lb,…) instead of explicitly referring to the MIP variables za,zb,….Figure 2
Example of node that is feasible connected w.r.t. its incoming arcs, but not w.r.t. Inequalities (3.22). Edges e1=e2=1/2 in the current LP-solutions, but as both edges have assigned the same label l1=12 the sum over the set of all labels assigned to incident edges of the considered node is also 1/2. Such situations are forbidden by Inequalities (3.22).This basic idea used in Inequalities (3.22) can be pursued by considering sets of two nodes, say v1 and v2. Let e12 denote the edge joining v1 and v2. Let further L(e12) denote the set of labels associated with this edge. For set L(v1)∪L(v2), we can observe, that at least two labels are required to feasibly connect the nodes v1 and v2, if L(v1)∩L(v2)=∅. However, if L(v1)∩L(v2)=L(e12), we still require two labels from L(v1)∪L(v2). We therefore obtain the following valid inequalities:(3.23)∑l∈L(v1)∪L(v2)zl≥2,∀v1,v2∈VwithL(v1)∩L(v2)=L(e12),
which are not directly implied by Inequalities (3.22). Figure 3 shows an example where Inequalities (3.23) dominate Inequalities (3.22).Figure 3
Example of node-label-constraints for sets of two nodes (3.23) dominating Inequalities (3.22), that is, the node-label constraints for single nodes. For both nodes vi, i=1,2 it holds that ∑l∈L(vi)l≥1. Corresponding Inequality (3.23) is however violated, as ∑l∈L(v1)∪L(v2)l=3/2.As we can expect a lot of branching on the label variables, further cutting-planes cutting of fractional label solutions may be helpful. In order to identify such valid inequalities, we consider situations where fractional label variables lower the objective value of LP solutions. Such a situation is depicted in Figure4. If labels a=b=c=1/2 in the LP solutions, the corresponding arcs can be set to 1/2 as well without violating any directed connectivity inequality. However, w.r.t. these arc set, at least two labels must be selected in an integer solution. Consequently, adding the inequality a+b+c≥2 will cut off this fractional solution, but is only valid if no additional arcs/edges are incident to these nodes.Figure 4
Example of fractional label solution.In the following we show how to applyodd hole inequalities to cut-off such and more general situations. These inequalities are well known from studies of the set-covering polytope, their application becomes evident by the observation that the MLST problem can be seen as a set covering problem where each nodev needs to be covered by a label from the set L(v) and the corresponding edges fulfilling further constraints (i.e., forming a valid spanning tree). In particular, we use a MIP-based heuristic to separate valid inequalities for the set-covering problem with coefficients {0,1}, which have been proposed in [24].LetΛ be a |V|×|L| matrix with λij=1 if node i is labeled with j, λij=0 otherwise. A |V′|×|L′| submatrix Λ′ of Λ of odd order is called an odd hole if it contains exactly two ones per row and column. For the subproblem Λ′z′≥1 the inequality(3.24)∑l∈L′zl≥|L′|+12
is valid. In [24] the authors showed that this inequality even remains valid if H≤Λ′≤H*, where H is an odd hole, and H* being a special matrix closely related to H. Finding an odd hole H to a given matrix Λ′ is 𝒩𝒫-hard, but if we have found such an odd hole, it is possible to decide in polynomial time whether H≤Λ′≤H* and therefore (3.24) is valid [24].


#### 3.3.1. Separation-Heuristic for the Odd Hole Inequalities

In order to cut off fractional label solutions, we consider the subset of nodesV′′⊆V whose labels are either fractional or zero in the current LP solution. Let Λ̃V′′ denote the matrix where each entry λij represents the current LP value of label j associated to node i, or −1 if the label j is not associated to node i. Let further ΛV′′ denote the corresponding matrix representing which labels are assigned to particular nodes, that is, its elements λijV′′ are one if label j∈L(δ(i)), and zero otherwise. Our goal is to heuristically search for odd holes in ΛV′′, based on the information provided by matrix Λ̃V′′, and then transform the related inequality to a valid inequality for the initial problem by the according lifting steps. We are hence searching for an odd hole H with H≤ΛV′,L′ with V′⊆V′′,L′⊆L′′ and |V′|=|L′| being odd. By the procedure of [24] we can now decide if(3.25)∑l∈L′′∖L′γl⋅zl+∑l∈L′zl≥|L′|+12
is valid for ΛV′,L′. The term ∑l∈L′′∖L′γl·zl results from lifting all labels which are associated to a node v∈V′ but are not part of the odd hole induced by V′ and L′. The lifting-coefficient is denoted by γl, the calculation of its value will be discussed later on. By the following MIP (3.26)–(3.38) we aim to find subsets V′ and L′ forming an odd hole and for which inequality (3.25) is violated according to the current LP solution. For this purpose we define a bipartite directed graph G̃=(Ṽ=Ṽ1∪Ṽ2,Ã), Ṽ1=V′′, Ṽ2=L′′, Ã={(i,j)∣i∈V′′∧j∈L′′(V′′)}. Each cycle with length 4·k+2 corresponds to an odd cycle w.r.t. the number labels, and is, therefore, a potential odd hole. Variables xij∈{0,1} represent the arcs from node i∈V′′ to label j∈L′′(V′′) and are intended to finally describe a valid odd hole. Variables aij∈[0,1] denote other arcs which connect nodes i∈V′′ being part of the odd hole (described by the x variables) and other labels not being part of the odd hole. For each arc a=(i,j) the coefficient ca is the LP value of label j if j∈L′ and zero otherwise;(3.26)max⁡k+1-∑i∈Ãxi⋅ci-∑i∈Ãai⋅ci,(3.27)s.t.k+1-∑i∈Ãxi⋅ci-∑i∈Ãai⋅ci≥0,(3.28)∑i∈Ãxi=4⋅k+2,(3.29)∑(i,j)∈δ-(j)xij≤1∀j∈L′′,(3.30)∑(i,j)∈δ+(i)xij≤1∀i∈V′′,(3.31)∑(i,j)∈Axij-∑(j,k)∈Axjk=0∀i∈Ṽ,(3.32)yi-yj+1+|Ṽ|⋅xij-|Ṽ|⋅zi≤|Ṽ|,(3.33)∑i∈Vzi≤1,(3.34)∑(k,i)∈δ-(i)xki-∑(j,l)∈δ-(j)xjl≤aij∀(i,j)∈Ã,(3.35)yi≤|Ṽ|∀i∈Ṽ,(3.36)zi∈{0,1}∀i∈Ṽ,(3.37)xi∈{0,1}∀i∈Ã,(3.38)0≤ai≤1∀i∈Ã.From (3.28), we can see that (|L′|+1)/2=k+1. As we prefer solutions where (3.25) is considerably violated, we maximize the difference between (|L′|+1)/2 and ∑i∈Ãxi·ci. The term ∑i∈Ãai·ci gives a lower bound for the sum over all labels we need to lift w.r.t. some particular x. The correct coefficient which is to be discussed later on, cannot be formulated by a linear expression. By (3.27), this particular expression is enforced to be larger than zero, as the resulting inequality to be added to the MLST-MIP would not be violated otherwise. As a consequence, all feasible solutions to MIP (3.26)–(3.38) fulfill this property which is desirable for the heuristic separation procedure discussed subsequently. For each node on the cycle, the numbers of ingoing and outgoing arcs are limited to one by equations (3.29) and (3.30) and flow-conservation is imposed for each node (3.31). The integer variables yi assign numeric values to the nodes i∈V′′∪L′′ and prevent multiple cycles in the solution by Miller-Tucker-Zemlin-inequalities (3.32), that is, by enforcing for each arc on the cycle (except the one going out from the node i with zi=1 (3.33)) to have at least one smaller source than target node. By Inequalities (3.34) all arcs connecting nodes i∈V′ which are part of the odd cycle to be determined (by x-variables) to nodes j∈L′′(i)not being part of this cycle. Finally, yi, for all i∈Ṽ are enforced to be smaller than |Ṽ| (3.35), and the node selection and arc variables are required to be Boolean (3.36), (3.37). The a-variables only need to be restricted to 0≤ai≤1, for all i∈Ã, as they are implicitly integer by Inequalities (3.34). Figure 5 shows an example for a solution to the MIP. The arcs selected by x-variables are depicted in red color, the dashed ones do not contribute to the objective function. The blue arcs correspond to the “lifting-arcs”, selected by a-variables.Figure 5
Example for a solution to (3.26)–(3.38). The octagon-shaped cycle constitutes the odd hole. The dashed arcs do not contribute to the objective function, whereas the solid arcs (which connect nodes to labels) contribute with the LP-value of the target-label as coefficient. The further arcs provide a lower bound for the contribution of all labels that need to be lifted in order to obtain a valid inequality for the initial problem.Given a solution to the MIP (3.26)–(3.38), we still need to check, if (3.25) is valid for this particular solution. The z-variables are derived by taking all labels j∈L′ selected by xij in (3.26)–(3.38). For this purpose, we use the criteria described in [24]—here we only provide a rough explanation. An arc connecting two nodes on the odd cycle determined by (3.26)–(3.38) which is not part of the cycle itself is called a chord. In order to fulfill (3.24), and therefore (3.25) after the lifting, all chords of the odd cycle must be compatible. The chord set is called compatible, if (1) no chord induces even cycles (w.r.t. nodes i∈V′ on the cycle), and (2) every pair of crossing chords is compatible. Compatibility for crossing chords is defined on the basis of the mutual distances of their adjacent nodes on the cycle. Let aij=(vi,lj),  vi∈V′, lj∈L′ and ahk=(vh,lk), vh∈V′, lk∈L′ be two crossing chords. We now remove lj and its two incident arcs from the odd hole. The chords are compatible, if the unique path from vi to vh has an even distance w.r.t. nodes in V′ in this graph.It remains to determine the lifting-coefficientsγl. If a lifting-label only covers one node of the odd hole, the sum over all labels necessary to feasibly cover all nodes from the odd hole does not change. The label can, however, be used alternatively for one of the odd hole labels and therefore gets coefficient one. Otherwise, if one lifting-label covers all odd hole nodes, the coefficient must equal the right-hand side of (3.25), that is,  γl=(|L′|+1)/2 in this case. Suppose some lifting-label l covers νl odd hole nodes, then the size of the remaining odd hole nodes is (|L′|+1)/2=⌈|L′|/2⌉. These remaining nodes are still adjacent to two labels in the odd hole, pairwise having one label in common. We can,  therefore, derive the following value for the lifting coefficient(3.39)γl=⌈|L′|2⌉-⌈|L′|-νl2⌉=|L′|+12-(|L′|+12-⌈νl2⌉)=⌈νl2⌉.During the branch-and-bound MLST solution process, the MIP (3.26)–(3.38) is solved with very tight runtime limits. As soon as an incumbent integer solution has been found, this solution is checked for validity by the mentioned criterions. Obtained valid MLST-inequalities are added immediately. Then the incumbent integer solution is rejected to the MIP solver by which we enforce to search for further solutions. This process continues until the time limit is reached.


### 3.4. Heuristics

In order to improve the overall performance—in particular the ability to generate feasible integer solutions fast—we embed a primal heuristic into the framework. For this purpose we adopt the well-known MVCA heuristic [1, 3, 6]. This heuristic can create feasible solutions from scratch, but also complete partial solutions given by label set L̃⊂L. Creating complete solutions is important for the acquisition of strong upper bounds to efficiently cut-off unprofitable branches of the B&B-tree from the beginning on, but also to obtain an initial solution for BCP (Section 3.5). On the other hand the MVCA heuristic can be used to obtain feasible integer solutions and therefore upper bounds for each B&B-node based upon some variables already fixed to integer values. Many further fast metaheuristic techniques do exist for this problem, which could also easily be integrated into this framework. This is however beyond the scope of this work, as we primarily focus on mathematical programming methods for the MLST.


### 3.5. Pricing Problem

Problem formulations with a large (usually exponential) number of variables are frequently solved by column generation or branch-and-price algorithms. Such algorithms start with a restricted set of variables and add potentially improving variables during the solution process on demand. If these algorithms also include cutting-plane generation, we call them branch-and-cut-and-price (BCP). Although the presented MLST formulation only has a polynomial number of label variables, these particular variables typically lead to extensive branching on them, requiring a special treatment. Hence we based a solution approach on BCP, operating on just a subset of variables. Such approaches follow the same idea as sparse graph techniques as proposed in [25].We obtain therestricted master problem by replacing the complete set of labels L by a subset L′⊆L in (3.1). The set L′ is required to imply a feasible solution and is obtained by the MVCA heuristic. Then, new variables and, therefore, columns potentially improving the current objective function value in the simplex tableau are created during the B&B process. These new variables are obtained from the solution of the pricing problem which is based upon the dual variables. Let πi denote the dual variables corresponding to constraints (3.2), and μi the ones corresponding to (3.22). They reflect a measure for the costs of some particular edge e w.r.t. the currently selected labels (πe), and the costs of connecting some node v w.r.t. the currently selected labels (μv). The pricing problem is to find a variable with negative reduced costs(3.40)c¯l=1-∑(i,j)∈A(l)πij-∑i∈V(l)μi,
within the set of all labels L. Here A(l) denotes all arcs having label l and V(l) denotes the set of nodes incident to arcs with label l. Finding such a variable or even the one with minimal reduced costs can be done by enumeration. Although only a polynomial number of labels is involved, we may benefit from the pricing scheme as we only need to solve smaller LPs within the B&B procedure.


### 3.6. Polyhedral Comparison

In this section we compare various formulations resulting from combining the equations and inequalities from Section3 as listed in Table 1. The only formulation just requiring a polynomial number of constraints is the flow-formulation with roughly O(|L|+3·|E|) variables and O(|L|+|V|+|E|) constraints. The directed cut-formulation requires O(|L|+3·|E|) variables and an exponential number of constraints. Also, the modified “epsilon” cut-formulation requires exponentially many constraints, but only has O(|L|+|E|) variables.Table 1
MLST formulations resulting from combining the equations and inequalities from Section3. Further variants are given by the use of the components listed in the second part of the table, to be used as index for the formulation to be used with.
AbbrevationInvolved equations and inequalitiesSCF(3.1), (3.2), (3.6)–(3.8)MCF(3.1), (3.2), (3.5), (3.9), (3.8)DCut(3.1), (3.2), (3.5), (3.11), (3.12), (3.13), (3.14)EC(3.1), (3.2), (3.5), (3.20), (3.18)MTZ(3.1), (3.2), (3.16)CEF(3.1), (3.2), (3.15)nNode-label-constraints (3.22)ñExtended node-label-constraints (3.23)tTree search, that is, fixed number of edges (3.5)sStrong linkage (3.21)cCycle elimination inequalities (3.15)oOdd hole inequalitiespVariable pricingIn the following we use the graph depicted in Figure6 to show the properties of the polyhedra defined by the formulations listed in Table 1.Figure 6
Example graph used in the following to show the properties of the formulations listed in Table1. The set of labels is given by L={a,b,c,d,e}, the optimal solution value is f=3.Proposition 3.2.
(3.41)PSCFtno⊊PSCFtn⊊PSCFt⊊PSCF.Proof.
AsPSCFtn contains the same equations and inequalities as PSCFt, but additionally Inequalities (3.22); thus we have PSCFtn⊆PSCFt. Figure 7 shows an LP solution of PSCFt that is not contained in PSCFtn, which implies PSCFtn⊊PSCFt. Such an LP solution may still contain fractional labels due to odd holes, as shown in Figure 5, by which we obtain PSCFtno⊊PSCFtn.
If the values of the edge and label variables in Figure7 are decreased as much as possible for SCF, we obtain la=1/4,lb=38, and lc=1/8 implying flp=3/4. As SCFt contains the additional Inequality (3.5), we can conclude that PSCFt⊊PSCF.Figure 7
LP solution ofSCFt with objective value flp=1+5/8(la=1/4,lb=3/8,lc=1). The blue arcs depict the flow variables with their according LP-values. Corresponding values for the edge variables are also shown. This solution is not valid for SCFtn, as the sum over the set of labels adjacent to node v2 is smaller than one.Proposition 3.3.
(3.42)PDCuttno⊊PDCuttn⊊PDCutt⊊PDCut.Proof.
The proof ofPDCuttno⊊PDCuttn⊊PDCutt follows by the same reasoning as for the proof of Proposition 3.2. Figure 8 shows that PDCuttn⊊PDCutt. However, the requirement that each directed cut must have a value greater than one already implies that ∑e∈δ(v)xe≥1,  for all v∈V. This implies ∑e∈Exe≥|V|-1. An LP-solution to DCut may contain more edges than an LP-solution to DCutt, which does, however, due to the minimality not affecting the objective value of the LP-relaxation, that is, PzDCutt=PzDCut.Figure 8
LP solution ofDCutt with objective value flp=(2+1)/6(lb=1/2,lc=2/3,la+ld+le≥1,w.l.o.g.la=1). The green arcs depict the arc variables with their according LP values. The solution is not valid for DCuttn, as the sum over the set of labels adjacent to node v5 is smaller than one.LetPS denote the projection of some polyhedron P to a subspace S.Proposition 3.4.
(3.43)PxECtno⊊PxECtn⊊PxECt⊊PxEC.Proof.
By applying the same reasoning as for the proofs of the last two theorems, we can prove Proposition3.4. Figure 9 gives an example for PECtn⊈PECt.Figure 9
LP solution ofECt with objective value flp=3/2+ϵ(la=ϵ,lb=1/2,lc=1). The solution is not valid for ECtn, as the sum over the set of labels adjacent to nodes v1 and v2 are smaller than one.In the following we will show the relations between the formulationsSCFt, DCutt and ECt.Theorem 3.5.
(3.44)PxDCutt⊊PxSCFt⊊PxECt.Proof.
Figures8, 7, and 9 already showed that the polyhedrons are not equal. To prove that PxDCutt⊊PxSCFt, we show a procedure to transform all x-variables of any valid LP-solution of DCutt to a valid x-solution in SCFt. For all i,j∈V, there exists at least one path from i to j with all edges (k,l) having LP-values xkllp greater than zero. If we consider a network with source i and target j, only containing edges e being part of one of these paths and having capacities xelp there exists a flow of at least one unit from s to t. We now arbitrarily select a root node r (w.l.o.g. r=0) and show how to construct a valid flow permitting the same x-configuration for SCFt as in DCutt. For an edge e to have LP value xelp, a corresponding flow variable must be larger than xelp/(n-1). We start by setting all flow variables to zero. Then, for each node ti,i=1,…,n-1 we construct all paths from r to ti, considering all edges with xelp>0. Summing up xelp>0 for all edges e on these paths may not exceed n-1, as the number of edges is fixed by (3.5) when i=2. However, this sum may usually be smaller than n-1, say λl, but integer. Now, we backtrack all these paths and set their flow values to minimal values according to flow conservation (3.7) and LP-values for the edges. Note that ∑i∈δ(r)fri=λ1 after this first step. We then continue this procedure for all further ti,i=2,…,n-1. According to (3.5) in step tk at most (n-1)-∑l<kλk not yet considered edges need to be added, possibly increasing ∑i∈δ(r)fri by exactly this amount. We finally end up with all nodes being feasibly connected and ∑i∈δ(r)fri=(n-1) fulfilling (3.6) and flow conservation (3.7) being fulfilled at each node.
It is trivial to see that thex-variables of a valid LP-solution of SCFt are also valid for ECt.Theorem 3.6.
(3.45)PxDCuttn⊊PxSCFtn⊊PxECtn.Proof.
In the proof of Theorem3.5, we already showed how each projection of a solution of DCutt to the subspace defined by the x-variables can be transformed into a solution of SCFt, and likewise SCFt to ECt. The only difference of the polyhedrons considered in Theorem 3.6 are the constraints (3.22), which clearly do not affect this transformation. It needs to be shown that the polyhedrons are not equal, which is done by the example in Figure 10. The depicted ECtn solution is not valid for SCFtn or DCutn, respectively, although the node-label constraints (3.22) are fulfilled. However, the value of edge {3,4} can be increased to 1/5 (implying the need to decrease the values of edges {1,4} and {3,6} accordingly), which makes the solution feasible to SCFtn. Nevertheless, this solution remains infeasible to DCuttn, by which we have shown the theorem.Figure 10
Valid LP-solution ofECtn with flp=2+ϵ(la=1,lb=ϵ,lc=1) that is not valid for SCFtn. It can however be transformed to such, by increasing x3,4 to 1/5, yielding flp=2+1/5. It is easy to see, that this solution is still not valid for DCuttn.


## 3.1. Mixed Integer Formulation

The basic formulation is given by the following abstract integer linear program:(3.1)min⁡.∑l∈Lzl,(3.2)s.t.∑l∈L(e)zl≥xe,∀e∈E,(3.3)x≡spanning tree,(3.4)zl∈{0,1}∀l∈L.The objective function (3.1) minimizes the number of required labels, Inequalities (3.2) ensure that for each selected edge (at least) one label is selected. For the abstract condition (3.3), we will subsequently introduce alternative formulations.The number of selected edges may be fixed according to a valid spanning tree:(3.5)∑e∈Exe=|V|-1.
Note, that (3.5) is however not required for a valid description of the MLST problem.


### 3.1.1. Single-Commodity Flow Formulation

A single-commodity flow formulation, also considered in [16], is given as follows:(3.6)∑(0,i)∈Af0i=|V|-1,(3.7)∑(i,t)∈Afit-∑(t,j)∈Aftj=1∀t∈V∖{0},(3.8)fij≤(|V|-1)⋅xe∀{i,j}∈E,e={i,j}.Equation (3.6) ensures the correct quantity of flow leaving the (arbitrary) root node with index 0. For all other nodes flow consumption (3.7) must hold, that is, one unit of flow is consumed at each node. Inequalities (3.8) finally ensure that only edges with a sufficient amount of flow may be selected. Flow formulations have the big advantage that they permit to formulate a spanning tree by a polynomial number of variables and therefore provide a relatively compact model.


### 3.1.2. Multicommodity Flow Formulation

The single-commodity flow formulation's major shortcoming is, however, that it provides a relatively poor LP-relaxation [19]. This is particularly due to the weak coupling of f to x-variables in Inequalities (3.8), the linking constraints. This drawback can be circumvented by the introduction of multiple commodities k for each node v∈V. Again, all flows of commodity k originate from node 0 and must be delivered to node k. The formulation is given by the following equalities:(3.9)∑(i,t)∈Afitk-∑(t,j)∈Aftjk={-1,t=0,0,t≠0∧t≠k,1,t=k.∀k∈V∖{0},
Linkage of flow to edge variables is then given by(3.10)xe≤fijk∀commoditiesk,∀e={i,j}∈E.This formulation, however, has the drawback of having more variables than the single-commodity flow formulation, that is,O(|V|·|E|) flow variables in contrast to only O(|E|).


### 3.1.3. Directed Cut Formulation

An alternative formulation is given by directed-connection inequalities, stating that to each node a valid (directed) path must exist. In contrast to the flow model, this formulation consists of an exponential number of inequalities and therefore cannot be directly passed to an ILP-solver for larger instances. However, this formulation provides a better LP-relaxation to many spanning tree problems, as it exactly describes the convex hull of the minimum spanning tree polyhedron. The corresponding inequalities, linkage to the edge variables are given by the following:(3.11)∑(i,j)∈δ-(S)yij≥1∀S⊆V,0∉S,(3.12)xe≥yij∀{i,j}∈E,e={i,j}.Hereδ-(S) denotes the set of ingoing arcs to some node set S⊂V. Instead of Inequalities (3.12) we could also directly link the labels to the directed arcs. However, we proceed with Inequalities (3.12) for sake of a unified notation. The separation of these directed-connection inequalities is discussed in Section 3.2.It is well known to be practically advantageous to initially add the inequalities(3.13)yij+yji≤1,∀{i,j}∈E,(3.14)∑(i,j)∈δ-(j)yij≥1,∀j∈V∖{0},
to directed (cut-based) formulations, see [20, 21]. Inequalities (3.13) avoid short cycles corresponding to a single edge, Inequalities (3.14) assure that each node has one incoming arc. By δ-(i) we denote the set of incoming arcs to node i.


### 3.1.4. Cycle-Elimination Formulation

We can also ensure feasibility for integer solutions bycycle-elimination inequalities. These inequalities enforce the resulting graph not to contain any cycles, which is together with the enforced number of arcs also a sufficient condition for spanning trees, and is given by the following Inequalities:(3.15)∑e∈Cxe≤|C|-1,∀cyclesC∈G,|C|>2.


### 3.1.5. Miller-Tucker-Zemlin Formulation

A further way for prohibiting cycles is models based on the well-knownMiller-Tucker-Zemlin inequalities [22]. Such a model for the MLST problem has been proposed in [15], however with some differences. Let ui∈ℝ for all i∈V denote variables assigning numeric values to each node. By inequalities(3.16)ui-uj+|V|⋅yij≤|V|-1∀(i,j)∈A,(3.17)ui≤|V|∀i∈V,
cycles can be inhibited by just using a polynomial number of variables, however with the drawback, that a large multiplicative factor appears, usually leading to bad LP-relaxations. Main difference to the formulation proposed in [15] is the meaning of the variables. Whereas we use distinct variables for labels and edges (O(|E|+|L|) variables), and link them by Inequalities (3.8) which are in total O(|E|) constraints, they introduce O(|E|·|L|) variables xijk with i, j corresponding to edges {i,j} and index k corresponding to labels.In [16], the authors pointed out an important property of the flow formulation. They showed that the edge variables are not required to be an integer in order to obtain the correct (optimal) objective function value. Furthermore it is easy to derive a valid MLST solution based on the set of labels provided by the MIP solution. Based on this reasoning, we can establish the following theorem, which extends this result to further MLST formulations, and also immediately provides an improved cut formulation with a fast separation method.


### 3.1.6. Epsilon-Connectivity Formulation

Theorem 3.1.
For any MIP formulation given by (3.1), (3.2) and (3.5), zl∈{0,1}, for all l∈L any set of labels corresponding to an optimal solution to this formulation, and additionally meeting the following inequalities “epsilon-connectivity”
(3.18)∑e∈δ(S)xe≥ϵ∀S⊂V,S≠∅
implies a valid MLST. Here, ϵ>0 denotes some arbitrary small real number.Proof.
The number of edges is fixed by (3.5), but a solution may still contain fractional edges. However, as the label variables z are integer and required to be greater than the value of the corresponding edge variables by Inequalities (3.2), they are always one if the corresponding edge variable has a value greater than ϵ. Consequently, fractional edge variables will only appear in the final solution if they do not raise the objective function value (by requiring additional labels). Due to Inequalities (3.18), the labels obtained from the MIP solution facilitate paths between all pairs of nodes.Given a label set of an optimal MIP solution, a feasible spanning tree can easily be derived in polynomial time, by determining an arbitrary spanning tree on the edges induced by the label set, as described in [16]. As a direct consequence of Theorem 3.1, the domain of the variables x and y need not be restricted to Boolean values, restricting them to nonnegative values by inequalities(3.19)xe≥0,∀e∈E,yi,j≥0,∀{i,j}∈E,yj,i≥0,∀{i,j}∈E,
is already sufficient.Theorem3.1 also suggests a further formulation for the MLST problem. Although not explicitly containing any constraints describing a valid spanning tree, (3.1), (3.2), (3.5), and (3.18) already provide a complete description to the MLST problem, and could be further strengthened by(3.20)∑e∈δ(i)xe≥1,∀i∈V,
and Inequalities (3.22), which are defined later on in Section 3.3. Inequalities (3.18) will again be separated on demand as cutting planes, which can, however, be performed more efficiently than the separation for the directed connection cuts, which will be discussed in detail in Section 3.2.Note that epsilon-connectivity as defined by Theorem3.1 is not guaranteed if cycle-elimination Inequalities (3.15) are used exclusively to describe a valid spanning tree. A fractional LP-solution not containing a cycle may still contain a subtour, that is, a subgraph where the sum over corresponding edges is larger than the size of its nodes minus one. Such a situation is depicted in Figure 1. As a consequence, the domain of the x-variables must be restricted to Boolean values if only cycle-elimination inequalities are used to describe a valid spanning tree. The same is true for the Miller-Tucker-Zemlin formulation given by Inequalities (3.16).Figure 1
LP-solution that does not contain a cycle w.r.t. Inequalities (3.15), but still violates subtour elimination constraints. Corresponding (integer) label solutions are not necessarily feasible.We now draw our attention to the special case of having only one single label assigned to each edge. If we have not fixed the number of edges, we can impose further equalities(3.21)∑l∈L(e)zl=xe,∀e∈E,
instead of Inequalities (3.2), which provide a more direct link between labels and their corresponding edges. This approach emphasizes the search for a feasible label set of minimal cardinality rather then the search for a feasible spanning tree.


## 3.1.1. Single-Commodity Flow Formulation

A single-commodity flow formulation, also considered in [16], is given as follows:(3.6)∑(0,i)∈Af0i=|V|-1,(3.7)∑(i,t)∈Afit-∑(t,j)∈Aftj=1∀t∈V∖{0},(3.8)fij≤(|V|-1)⋅xe∀{i,j}∈E,e={i,j}.Equation (3.6) ensures the correct quantity of flow leaving the (arbitrary) root node with index 0. For all other nodes flow consumption (3.7) must hold, that is, one unit of flow is consumed at each node. Inequalities (3.8) finally ensure that only edges with a sufficient amount of flow may be selected. Flow formulations have the big advantage that they permit to formulate a spanning tree by a polynomial number of variables and therefore provide a relatively compact model.


## 3.1.2. Multicommodity Flow Formulation

The single-commodity flow formulation's major shortcoming is, however, that it provides a relatively poor LP-relaxation [19]. This is particularly due to the weak coupling of f to x-variables in Inequalities (3.8), the linking constraints. This drawback can be circumvented by the introduction of multiple commodities k for each node v∈V. Again, all flows of commodity k originate from node 0 and must be delivered to node k. The formulation is given by the following equalities:(3.9)∑(i,t)∈Afitk-∑(t,j)∈Aftjk={-1,t=0,0,t≠0∧t≠k,1,t=k.∀k∈V∖{0},
Linkage of flow to edge variables is then given by(3.10)xe≤fijk∀commoditiesk,∀e={i,j}∈E.This formulation, however, has the drawback of having more variables than the single-commodity flow formulation, that is,O(|V|·|E|) flow variables in contrast to only O(|E|).


## 3.1.3. Directed Cut Formulation

An alternative formulation is given by directed-connection inequalities, stating that to each node a valid (directed) path must exist. In contrast to the flow model, this formulation consists of an exponential number of inequalities and therefore cannot be directly passed to an ILP-solver for larger instances. However, this formulation provides a better LP-relaxation to many spanning tree problems, as it exactly describes the convex hull of the minimum spanning tree polyhedron. The corresponding inequalities, linkage to the edge variables are given by the following:(3.11)∑(i,j)∈δ-(S)yij≥1∀S⊆V,0∉S,(3.12)xe≥yij∀{i,j}∈E,e={i,j}.Hereδ-(S) denotes the set of ingoing arcs to some node set S⊂V. Instead of Inequalities (3.12) we could also directly link the labels to the directed arcs. However, we proceed with Inequalities (3.12) for sake of a unified notation. The separation of these directed-connection inequalities is discussed in Section 3.2.It is well known to be practically advantageous to initially add the inequalities(3.13)yij+yji≤1,∀{i,j}∈E,(3.14)∑(i,j)∈δ-(j)yij≥1,∀j∈V∖{0},
to directed (cut-based) formulations, see [20, 21]. Inequalities (3.13) avoid short cycles corresponding to a single edge, Inequalities (3.14) assure that each node has one incoming arc. By δ-(i) we denote the set of incoming arcs to node i.


## 3.1.4. Cycle-Elimination Formulation

We can also ensure feasibility for integer solutions bycycle-elimination inequalities. These inequalities enforce the resulting graph not to contain any cycles, which is together with the enforced number of arcs also a sufficient condition for spanning trees, and is given by the following Inequalities:(3.15)∑e∈Cxe≤|C|-1,∀cyclesC∈G,|C|>2.


## 3.1.5. Miller-Tucker-Zemlin Formulation

A further way for prohibiting cycles is models based on the well-knownMiller-Tucker-Zemlin inequalities [22]. Such a model for the MLST problem has been proposed in [15], however with some differences. Let ui∈ℝ for all i∈V denote variables assigning numeric values to each node. By inequalities(3.16)ui-uj+|V|⋅yij≤|V|-1∀(i,j)∈A,(3.17)ui≤|V|∀i∈V,
cycles can be inhibited by just using a polynomial number of variables, however with the drawback, that a large multiplicative factor appears, usually leading to bad LP-relaxations. Main difference to the formulation proposed in [15] is the meaning of the variables. Whereas we use distinct variables for labels and edges (O(|E|+|L|) variables), and link them by Inequalities (3.8) which are in total O(|E|) constraints, they introduce O(|E|·|L|) variables xijk with i, j corresponding to edges {i,j} and index k corresponding to labels.In [16], the authors pointed out an important property of the flow formulation. They showed that the edge variables are not required to be an integer in order to obtain the correct (optimal) objective function value. Furthermore it is easy to derive a valid MLST solution based on the set of labels provided by the MIP solution. Based on this reasoning, we can establish the following theorem, which extends this result to further MLST formulations, and also immediately provides an improved cut formulation with a fast separation method.


## 3.1.6. Epsilon-Connectivity Formulation

Theorem 3.1.
For any MIP formulation given by (3.1), (3.2) and (3.5), zl∈{0,1}, for all l∈L any set of labels corresponding to an optimal solution to this formulation, and additionally meeting the following inequalities “epsilon-connectivity”
(3.18)∑e∈δ(S)xe≥ϵ∀S⊂V,S≠∅
implies a valid MLST. Here, ϵ>0 denotes some arbitrary small real number.Proof.
The number of edges is fixed by (3.5), but a solution may still contain fractional edges. However, as the label variables z are integer and required to be greater than the value of the corresponding edge variables by Inequalities (3.2), they are always one if the corresponding edge variable has a value greater than ϵ. Consequently, fractional edge variables will only appear in the final solution if they do not raise the objective function value (by requiring additional labels). Due to Inequalities (3.18), the labels obtained from the MIP solution facilitate paths between all pairs of nodes.Given a label set of an optimal MIP solution, a feasible spanning tree can easily be derived in polynomial time, by determining an arbitrary spanning tree on the edges induced by the label set, as described in [16]. As a direct consequence of Theorem 3.1, the domain of the variables x and y need not be restricted to Boolean values, restricting them to nonnegative values by inequalities(3.19)xe≥0,∀e∈E,yi,j≥0,∀{i,j}∈E,yj,i≥0,∀{i,j}∈E,
is already sufficient.Theorem3.1 also suggests a further formulation for the MLST problem. Although not explicitly containing any constraints describing a valid spanning tree, (3.1), (3.2), (3.5), and (3.18) already provide a complete description to the MLST problem, and could be further strengthened by(3.20)∑e∈δ(i)xe≥1,∀i∈V,
and Inequalities (3.22), which are defined later on in Section 3.3. Inequalities (3.18) will again be separated on demand as cutting planes, which can, however, be performed more efficiently than the separation for the directed connection cuts, which will be discussed in detail in Section 3.2.Note that epsilon-connectivity as defined by Theorem3.1 is not guaranteed if cycle-elimination Inequalities (3.15) are used exclusively to describe a valid spanning tree. A fractional LP-solution not containing a cycle may still contain a subtour, that is, a subgraph where the sum over corresponding edges is larger than the size of its nodes minus one. Such a situation is depicted in Figure 1. As a consequence, the domain of the x-variables must be restricted to Boolean values if only cycle-elimination inequalities are used to describe a valid spanning tree. The same is true for the Miller-Tucker-Zemlin formulation given by Inequalities (3.16).Figure 1
LP-solution that does not contain a cycle w.r.t. Inequalities (3.15), but still violates subtour elimination constraints. Corresponding (integer) label solutions are not necessarily feasible.We now draw our attention to the special case of having only one single label assigned to each edge. If we have not fixed the number of edges, we can impose further equalities(3.21)∑l∈L(e)zl=xe,∀e∈E,
instead of Inequalities (3.2), which provide a more direct link between labels and their corresponding edges. This approach emphasizes the search for a feasible label set of minimal cardinality rather then the search for a feasible spanning tree.


## 3.2. Cutting-Plane Separation

The directed connection Inequalities (3.11) can be separated by computing the maximum flow from the root node r to each node i as target node. This provides a minimum (r,i)-cut. We have found a violated inequality if the value of the corresponding arcs according to the sum of the LP-values is less than 1. Our separation procedure utilizes Cherkassky and Goldberg's implementation of the push-relabel method for the maximum flow problem [23] to perform the required minimum cut computations.The cycle-elimination cuts (3.15) can be easily separated by shortest path computations with Dijkstra's algorithm. Hereby we use 1-yijLP as the arc weights with yijLP denoting the current value of the LP-relaxation for arc (i,j) in the current node of the B&B-tree. We obtain cycles by iteratively considering each arc (i,j)∈A and searching for the shortest path from j to i. If the value of a shortest path plus yijLP is less than 1, we have found a cycle violating Inequalities (3.15). We add this inequality to the LP and resolve it. In each node of the B&B-tree, we perform these cutting plane separations until no further cuts can be found.Theorem3.1 suggested a formulation not requiring any auxiliary variables (like flow or arc variables), where validity of the labels is obtained by Inequalities (3.18) exclusively. Instead of using the minimum cut-based separation routine (which would also be valid), we can perform a faster separation by a simple depth first search (DFS). Given an LP-solution, we first select an arbitrary start node for which we call the DFS procedure. Within this procedure we only consider edges e with xe≥ϵ. Within the DFS, we keep track of all visited nodes, if there are unvisited nodes at the end of the DFS, we have found a valid cut. The DFS can be carried out in O(|V|+|E|) time, which is clearly superior to the time of the maximum flow algorithm running in O(|V|·|E|+|V|2+ε).


## 3.3. Strengthening the Formulations

As each node must be connected to the spanning tree by one of its incident edges, we can further impose additional inequalities to strengthen the formulation w.r.t. the label variables:(3.22)∑l∈L(v)zl≥1,∀v∈V.
Here, L(v), v∈V denotes the set of labels being associated to the edges incident to node v. We will subsequently refer to this set of |V| inequalities as node-label-inequalities. Figure 2 gives a simple example of an LP solution where the node is sufficiently connected according to the sum of the LP-values of the ingoing arcs and therefore its incident edges, but the corresponding sum over the labels associated to these edges is clearly infeasible w.r.t. Inequalities (3.22). Therefore Inequalities (3.22) strengthen the presented formulations w.r.t. their LP-relaxation. In Section 3.6, we formally prove this property with respect to the particular proposed MIP-formulations for the MLST. Note, that we will use MIP variables and their corresponding graph-entities equivalently in the the context of subsequent figures and proofs for simplicity, for example, we will simply designate a label by a,b,… (or la,lb,…) instead of explicitly referring to the MIP variables za,zb,….Figure 2
Example of node that is feasible connected w.r.t. its incoming arcs, but not w.r.t. Inequalities (3.22). Edges e1=e2=1/2 in the current LP-solutions, but as both edges have assigned the same label l1=12 the sum over the set of all labels assigned to incident edges of the considered node is also 1/2. Such situations are forbidden by Inequalities (3.22).This basic idea used in Inequalities (3.22) can be pursued by considering sets of two nodes, say v1 and v2. Let e12 denote the edge joining v1 and v2. Let further L(e12) denote the set of labels associated with this edge. For set L(v1)∪L(v2), we can observe, that at least two labels are required to feasibly connect the nodes v1 and v2, if L(v1)∩L(v2)=∅. However, if L(v1)∩L(v2)=L(e12), we still require two labels from L(v1)∪L(v2). We therefore obtain the following valid inequalities:(3.23)∑l∈L(v1)∪L(v2)zl≥2,∀v1,v2∈VwithL(v1)∩L(v2)=L(e12),
which are not directly implied by Inequalities (3.22). Figure 3 shows an example where Inequalities (3.23) dominate Inequalities (3.22).Figure 3
Example of node-label-constraints for sets of two nodes (3.23) dominating Inequalities (3.22), that is, the node-label constraints for single nodes. For both nodes vi, i=1,2 it holds that ∑l∈L(vi)l≥1. Corresponding Inequality (3.23) is however violated, as ∑l∈L(v1)∪L(v2)l=3/2.As we can expect a lot of branching on the label variables, further cutting-planes cutting of fractional label solutions may be helpful. In order to identify such valid inequalities, we consider situations where fractional label variables lower the objective value of LP solutions. Such a situation is depicted in Figure4. If labels a=b=c=1/2 in the LP solutions, the corresponding arcs can be set to 1/2 as well without violating any directed connectivity inequality. However, w.r.t. these arc set, at least two labels must be selected in an integer solution. Consequently, adding the inequality a+b+c≥2 will cut off this fractional solution, but is only valid if no additional arcs/edges are incident to these nodes.Figure 4
Example of fractional label solution.In the following we show how to applyodd hole inequalities to cut-off such and more general situations. These inequalities are well known from studies of the set-covering polytope, their application becomes evident by the observation that the MLST problem can be seen as a set covering problem where each nodev needs to be covered by a label from the set L(v) and the corresponding edges fulfilling further constraints (i.e., forming a valid spanning tree). In particular, we use a MIP-based heuristic to separate valid inequalities for the set-covering problem with coefficients {0,1}, which have been proposed in [24].LetΛ be a |V|×|L| matrix with λij=1 if node i is labeled with j, λij=0 otherwise. A |V′|×|L′| submatrix Λ′ of Λ of odd order is called an odd hole if it contains exactly two ones per row and column. For the subproblem Λ′z′≥1 the inequality(3.24)∑l∈L′zl≥|L′|+12
is valid. In [24] the authors showed that this inequality even remains valid if H≤Λ′≤H*, where H is an odd hole, and H* being a special matrix closely related to H. Finding an odd hole H to a given matrix Λ′ is 𝒩𝒫-hard, but if we have found such an odd hole, it is possible to decide in polynomial time whether H≤Λ′≤H* and therefore (3.24) is valid [24].


### 3.3.1. Separation-Heuristic for the Odd Hole Inequalities

In order to cut off fractional label solutions, we consider the subset of nodesV′′⊆V whose labels are either fractional or zero in the current LP solution. Let Λ̃V′′ denote the matrix where each entry λij represents the current LP value of label j associated to node i, or −1 if the label j is not associated to node i. Let further ΛV′′ denote the corresponding matrix representing which labels are assigned to particular nodes, that is, its elements λijV′′ are one if label j∈L(δ(i)), and zero otherwise. Our goal is to heuristically search for odd holes in ΛV′′, based on the information provided by matrix Λ̃V′′, and then transform the related inequality to a valid inequality for the initial problem by the according lifting steps. We are hence searching for an odd hole H with H≤ΛV′,L′ with V′⊆V′′,L′⊆L′′ and |V′|=|L′| being odd. By the procedure of [24] we can now decide if(3.25)∑l∈L′′∖L′γl⋅zl+∑l∈L′zl≥|L′|+12
is valid for ΛV′,L′. The term ∑l∈L′′∖L′γl·zl results from lifting all labels which are associated to a node v∈V′ but are not part of the odd hole induced by V′ and L′. The lifting-coefficient is denoted by γl, the calculation of its value will be discussed later on. By the following MIP (3.26)–(3.38) we aim to find subsets V′ and L′ forming an odd hole and for which inequality (3.25) is violated according to the current LP solution. For this purpose we define a bipartite directed graph G̃=(Ṽ=Ṽ1∪Ṽ2,Ã), Ṽ1=V′′, Ṽ2=L′′, Ã={(i,j)∣i∈V′′∧j∈L′′(V′′)}. Each cycle with length 4·k+2 corresponds to an odd cycle w.r.t. the number labels, and is, therefore, a potential odd hole. Variables xij∈{0,1} represent the arcs from node i∈V′′ to label j∈L′′(V′′) and are intended to finally describe a valid odd hole. Variables aij∈[0,1] denote other arcs which connect nodes i∈V′′ being part of the odd hole (described by the x variables) and other labels not being part of the odd hole. For each arc a=(i,j) the coefficient ca is the LP value of label j if j∈L′ and zero otherwise;(3.26)max⁡k+1-∑i∈Ãxi⋅ci-∑i∈Ãai⋅ci,(3.27)s.t.k+1-∑i∈Ãxi⋅ci-∑i∈Ãai⋅ci≥0,(3.28)∑i∈Ãxi=4⋅k+2,(3.29)∑(i,j)∈δ-(j)xij≤1∀j∈L′′,(3.30)∑(i,j)∈δ+(i)xij≤1∀i∈V′′,(3.31)∑(i,j)∈Axij-∑(j,k)∈Axjk=0∀i∈Ṽ,(3.32)yi-yj+1+|Ṽ|⋅xij-|Ṽ|⋅zi≤|Ṽ|,(3.33)∑i∈Vzi≤1,(3.34)∑(k,i)∈δ-(i)xki-∑(j,l)∈δ-(j)xjl≤aij∀(i,j)∈Ã,(3.35)yi≤|Ṽ|∀i∈Ṽ,(3.36)zi∈{0,1}∀i∈Ṽ,(3.37)xi∈{0,1}∀i∈Ã,(3.38)0≤ai≤1∀i∈Ã.From (3.28), we can see that (|L′|+1)/2=k+1. As we prefer solutions where (3.25) is considerably violated, we maximize the difference between (|L′|+1)/2 and ∑i∈Ãxi·ci. The term ∑i∈Ãai·ci gives a lower bound for the sum over all labels we need to lift w.r.t. some particular x. The correct coefficient which is to be discussed later on, cannot be formulated by a linear expression. By (3.27), this particular expression is enforced to be larger than zero, as the resulting inequality to be added to the MLST-MIP would not be violated otherwise. As a consequence, all feasible solutions to MIP (3.26)–(3.38) fulfill this property which is desirable for the heuristic separation procedure discussed subsequently. For each node on the cycle, the numbers of ingoing and outgoing arcs are limited to one by equations (3.29) and (3.30) and flow-conservation is imposed for each node (3.31). The integer variables yi assign numeric values to the nodes i∈V′′∪L′′ and prevent multiple cycles in the solution by Miller-Tucker-Zemlin-inequalities (3.32), that is, by enforcing for each arc on the cycle (except the one going out from the node i with zi=1 (3.33)) to have at least one smaller source than target node. By Inequalities (3.34) all arcs connecting nodes i∈V′ which are part of the odd cycle to be determined (by x-variables) to nodes j∈L′′(i)not being part of this cycle. Finally, yi, for all i∈Ṽ are enforced to be smaller than |Ṽ| (3.35), and the node selection and arc variables are required to be Boolean (3.36), (3.37). The a-variables only need to be restricted to 0≤ai≤1, for all i∈Ã, as they are implicitly integer by Inequalities (3.34). Figure 5 shows an example for a solution to the MIP. The arcs selected by x-variables are depicted in red color, the dashed ones do not contribute to the objective function. The blue arcs correspond to the “lifting-arcs”, selected by a-variables.Figure 5
Example for a solution to (3.26)–(3.38). The octagon-shaped cycle constitutes the odd hole. The dashed arcs do not contribute to the objective function, whereas the solid arcs (which connect nodes to labels) contribute with the LP-value of the target-label as coefficient. The further arcs provide a lower bound for the contribution of all labels that need to be lifted in order to obtain a valid inequality for the initial problem.Given a solution to the MIP (3.26)–(3.38), we still need to check, if (3.25) is valid for this particular solution. The z-variables are derived by taking all labels j∈L′ selected by xij in (3.26)–(3.38). For this purpose, we use the criteria described in [24]—here we only provide a rough explanation. An arc connecting two nodes on the odd cycle determined by (3.26)–(3.38) which is not part of the cycle itself is called a chord. In order to fulfill (3.24), and therefore (3.25) after the lifting, all chords of the odd cycle must be compatible. The chord set is called compatible, if (1) no chord induces even cycles (w.r.t. nodes i∈V′ on the cycle), and (2) every pair of crossing chords is compatible. Compatibility for crossing chords is defined on the basis of the mutual distances of their adjacent nodes on the cycle. Let aij=(vi,lj),  vi∈V′, lj∈L′ and ahk=(vh,lk), vh∈V′, lk∈L′ be two crossing chords. We now remove lj and its two incident arcs from the odd hole. The chords are compatible, if the unique path from vi to vh has an even distance w.r.t. nodes in V′ in this graph.It remains to determine the lifting-coefficientsγl. If a lifting-label only covers one node of the odd hole, the sum over all labels necessary to feasibly cover all nodes from the odd hole does not change. The label can, however, be used alternatively for one of the odd hole labels and therefore gets coefficient one. Otherwise, if one lifting-label covers all odd hole nodes, the coefficient must equal the right-hand side of (3.25), that is,  γl=(|L′|+1)/2 in this case. Suppose some lifting-label l covers νl odd hole nodes, then the size of the remaining odd hole nodes is (|L′|+1)/2=⌈|L′|/2⌉. These remaining nodes are still adjacent to two labels in the odd hole, pairwise having one label in common. We can,  therefore, derive the following value for the lifting coefficient(3.39)γl=⌈|L′|2⌉-⌈|L′|-νl2⌉=|L′|+12-(|L′|+12-⌈νl2⌉)=⌈νl2⌉.During the branch-and-bound MLST solution process, the MIP (3.26)–(3.38) is solved with very tight runtime limits. As soon as an incumbent integer solution has been found, this solution is checked for validity by the mentioned criterions. Obtained valid MLST-inequalities are added immediately. Then the incumbent integer solution is rejected to the MIP solver by which we enforce to search for further solutions. This process continues until the time limit is reached.


## 3.3.1. Separation-Heuristic for the Odd Hole Inequalities

In order to cut off fractional label solutions, we consider the subset of nodesV′′⊆V whose labels are either fractional or zero in the current LP solution. Let Λ̃V′′ denote the matrix where each entry λij represents the current LP value of label j associated to node i, or −1 if the label j is not associated to node i. Let further ΛV′′ denote the corresponding matrix representing which labels are assigned to particular nodes, that is, its elements λijV′′ are one if label j∈L(δ(i)), and zero otherwise. Our goal is to heuristically search for odd holes in ΛV′′, based on the information provided by matrix Λ̃V′′, and then transform the related inequality to a valid inequality for the initial problem by the according lifting steps. We are hence searching for an odd hole H with H≤ΛV′,L′ with V′⊆V′′,L′⊆L′′ and |V′|=|L′| being odd. By the procedure of [24] we can now decide if(3.25)∑l∈L′′∖L′γl⋅zl+∑l∈L′zl≥|L′|+12
is valid for ΛV′,L′. The term ∑l∈L′′∖L′γl·zl results from lifting all labels which are associated to a node v∈V′ but are not part of the odd hole induced by V′ and L′. The lifting-coefficient is denoted by γl, the calculation of its value will be discussed later on. By the following MIP (3.26)–(3.38) we aim to find subsets V′ and L′ forming an odd hole and for which inequality (3.25) is violated according to the current LP solution. For this purpose we define a bipartite directed graph G̃=(Ṽ=Ṽ1∪Ṽ2,Ã), Ṽ1=V′′, Ṽ2=L′′, Ã={(i,j)∣i∈V′′∧j∈L′′(V′′)}. Each cycle with length 4·k+2 corresponds to an odd cycle w.r.t. the number labels, and is, therefore, a potential odd hole. Variables xij∈{0,1} represent the arcs from node i∈V′′ to label j∈L′′(V′′) and are intended to finally describe a valid odd hole. Variables aij∈[0,1] denote other arcs which connect nodes i∈V′′ being part of the odd hole (described by the x variables) and other labels not being part of the odd hole. For each arc a=(i,j) the coefficient ca is the LP value of label j if j∈L′ and zero otherwise;(3.26)max⁡k+1-∑i∈Ãxi⋅ci-∑i∈Ãai⋅ci,(3.27)s.t.k+1-∑i∈Ãxi⋅ci-∑i∈Ãai⋅ci≥0,(3.28)∑i∈Ãxi=4⋅k+2,(3.29)∑(i,j)∈δ-(j)xij≤1∀j∈L′′,(3.30)∑(i,j)∈δ+(i)xij≤1∀i∈V′′,(3.31)∑(i,j)∈Axij-∑(j,k)∈Axjk=0∀i∈Ṽ,(3.32)yi-yj+1+|Ṽ|⋅xij-|Ṽ|⋅zi≤|Ṽ|,(3.33)∑i∈Vzi≤1,(3.34)∑(k,i)∈δ-(i)xki-∑(j,l)∈δ-(j)xjl≤aij∀(i,j)∈Ã,(3.35)yi≤|Ṽ|∀i∈Ṽ,(3.36)zi∈{0,1}∀i∈Ṽ,(3.37)xi∈{0,1}∀i∈Ã,(3.38)0≤ai≤1∀i∈Ã.From (3.28), we can see that (|L′|+1)/2=k+1. As we prefer solutions where (3.25) is considerably violated, we maximize the difference between (|L′|+1)/2 and ∑i∈Ãxi·ci. The term ∑i∈Ãai·ci gives a lower bound for the sum over all labels we need to lift w.r.t. some particular x. The correct coefficient which is to be discussed later on, cannot be formulated by a linear expression. By (3.27), this particular expression is enforced to be larger than zero, as the resulting inequality to be added to the MLST-MIP would not be violated otherwise. As a consequence, all feasible solutions to MIP (3.26)–(3.38) fulfill this property which is desirable for the heuristic separation procedure discussed subsequently. For each node on the cycle, the numbers of ingoing and outgoing arcs are limited to one by equations (3.29) and (3.30) and flow-conservation is imposed for each node (3.31). The integer variables yi assign numeric values to the nodes i∈V′′∪L′′ and prevent multiple cycles in the solution by Miller-Tucker-Zemlin-inequalities (3.32), that is, by enforcing for each arc on the cycle (except the one going out from the node i with zi=1 (3.33)) to have at least one smaller source than target node. By Inequalities (3.34) all arcs connecting nodes i∈V′ which are part of the odd cycle to be determined (by x-variables) to nodes j∈L′′(i)not being part of this cycle. Finally, yi, for all i∈Ṽ are enforced to be smaller than |Ṽ| (3.35), and the node selection and arc variables are required to be Boolean (3.36), (3.37). The a-variables only need to be restricted to 0≤ai≤1, for all i∈Ã, as they are implicitly integer by Inequalities (3.34). Figure 5 shows an example for a solution to the MIP. The arcs selected by x-variables are depicted in red color, the dashed ones do not contribute to the objective function. The blue arcs correspond to the “lifting-arcs”, selected by a-variables.Figure 5
Example for a solution to (3.26)–(3.38). The octagon-shaped cycle constitutes the odd hole. The dashed arcs do not contribute to the objective function, whereas the solid arcs (which connect nodes to labels) contribute with the LP-value of the target-label as coefficient. The further arcs provide a lower bound for the contribution of all labels that need to be lifted in order to obtain a valid inequality for the initial problem.Given a solution to the MIP (3.26)–(3.38), we still need to check, if (3.25) is valid for this particular solution. The z-variables are derived by taking all labels j∈L′ selected by xij in (3.26)–(3.38). For this purpose, we use the criteria described in [24]—here we only provide a rough explanation. An arc connecting two nodes on the odd cycle determined by (3.26)–(3.38) which is not part of the cycle itself is called a chord. In order to fulfill (3.24), and therefore (3.25) after the lifting, all chords of the odd cycle must be compatible. The chord set is called compatible, if (1) no chord induces even cycles (w.r.t. nodes i∈V′ on the cycle), and (2) every pair of crossing chords is compatible. Compatibility for crossing chords is defined on the basis of the mutual distances of their adjacent nodes on the cycle. Let aij=(vi,lj),  vi∈V′, lj∈L′ and ahk=(vh,lk), vh∈V′, lk∈L′ be two crossing chords. We now remove lj and its two incident arcs from the odd hole. The chords are compatible, if the unique path from vi to vh has an even distance w.r.t. nodes in V′ in this graph.It remains to determine the lifting-coefficientsγl. If a lifting-label only covers one node of the odd hole, the sum over all labels necessary to feasibly cover all nodes from the odd hole does not change. The label can, however, be used alternatively for one of the odd hole labels and therefore gets coefficient one. Otherwise, if one lifting-label covers all odd hole nodes, the coefficient must equal the right-hand side of (3.25), that is,  γl=(|L′|+1)/2 in this case. Suppose some lifting-label l covers νl odd hole nodes, then the size of the remaining odd hole nodes is (|L′|+1)/2=⌈|L′|/2⌉. These remaining nodes are still adjacent to two labels in the odd hole, pairwise having one label in common. We can,  therefore, derive the following value for the lifting coefficient(3.39)γl=⌈|L′|2⌉-⌈|L′|-νl2⌉=|L′|+12-(|L′|+12-⌈νl2⌉)=⌈νl2⌉.During the branch-and-bound MLST solution process, the MIP (3.26)–(3.38) is solved with very tight runtime limits. As soon as an incumbent integer solution has been found, this solution is checked for validity by the mentioned criterions. Obtained valid MLST-inequalities are added immediately. Then the incumbent integer solution is rejected to the MIP solver by which we enforce to search for further solutions. This process continues until the time limit is reached.


## 3.4. Heuristics

In order to improve the overall performance—in particular the ability to generate feasible integer solutions fast—we embed a primal heuristic into the framework. For this purpose we adopt the well-known MVCA heuristic [1, 3, 6]. This heuristic can create feasible solutions from scratch, but also complete partial solutions given by label set L̃⊂L. Creating complete solutions is important for the acquisition of strong upper bounds to efficiently cut-off unprofitable branches of the B&B-tree from the beginning on, but also to obtain an initial solution for BCP (Section 3.5). On the other hand the MVCA heuristic can be used to obtain feasible integer solutions and therefore upper bounds for each B&B-node based upon some variables already fixed to integer values. Many further fast metaheuristic techniques do exist for this problem, which could also easily be integrated into this framework. This is however beyond the scope of this work, as we primarily focus on mathematical programming methods for the MLST.


## 3.5. Pricing Problem

Problem formulations with a large (usually exponential) number of variables are frequently solved by column generation or branch-and-price algorithms. Such algorithms start with a restricted set of variables and add potentially improving variables during the solution process on demand. If these algorithms also include cutting-plane generation, we call them branch-and-cut-and-price (BCP). Although the presented MLST formulation only has a polynomial number of label variables, these particular variables typically lead to extensive branching on them, requiring a special treatment. Hence we based a solution approach on BCP, operating on just a subset of variables. Such approaches follow the same idea as sparse graph techniques as proposed in [25].We obtain therestricted master problem by replacing the complete set of labels L by a subset L′⊆L in (3.1). The set L′ is required to imply a feasible solution and is obtained by the MVCA heuristic. Then, new variables and, therefore, columns potentially improving the current objective function value in the simplex tableau are created during the B&B process. These new variables are obtained from the solution of the pricing problem which is based upon the dual variables. Let πi denote the dual variables corresponding to constraints (3.2), and μi the ones corresponding to (3.22). They reflect a measure for the costs of some particular edge e w.r.t. the currently selected labels (πe), and the costs of connecting some node v w.r.t. the currently selected labels (μv). The pricing problem is to find a variable with negative reduced costs(3.40)c¯l=1-∑(i,j)∈A(l)πij-∑i∈V(l)μi,
within the set of all labels L. Here A(l) denotes all arcs having label l and V(l) denotes the set of nodes incident to arcs with label l. Finding such a variable or even the one with minimal reduced costs can be done by enumeration. Although only a polynomial number of labels is involved, we may benefit from the pricing scheme as we only need to solve smaller LPs within the B&B procedure.


## 3.6. Polyhedral Comparison

In this section we compare various formulations resulting from combining the equations and inequalities from Section3 as listed in Table 1. The only formulation just requiring a polynomial number of constraints is the flow-formulation with roughly O(|L|+3·|E|) variables and O(|L|+|V|+|E|) constraints. The directed cut-formulation requires O(|L|+3·|E|) variables and an exponential number of constraints. Also, the modified “epsilon” cut-formulation requires exponentially many constraints, but only has O(|L|+|E|) variables.Table 1
MLST formulations resulting from combining the equations and inequalities from Section3. Further variants are given by the use of the components listed in the second part of the table, to be used as index for the formulation to be used with.
AbbrevationInvolved equations and inequalitiesSCF(3.1), (3.2), (3.6)–(3.8)MCF(3.1), (3.2), (3.5), (3.9), (3.8)DCut(3.1), (3.2), (3.5), (3.11), (3.12), (3.13), (3.14)EC(3.1), (3.2), (3.5), (3.20), (3.18)MTZ(3.1), (3.2), (3.16)CEF(3.1), (3.2), (3.15)nNode-label-constraints (3.22)ñExtended node-label-constraints (3.23)tTree search, that is, fixed number of edges (3.5)sStrong linkage (3.21)cCycle elimination inequalities (3.15)oOdd hole inequalitiespVariable pricingIn the following we use the graph depicted in Figure6 to show the properties of the polyhedra defined by the formulations listed in Table 1.Figure 6
Example graph used in the following to show the properties of the formulations listed in Table1. The set of labels is given by L={a,b,c,d,e}, the optimal solution value is f=3.Proposition 3.2.
(3.41)PSCFtno⊊PSCFtn⊊PSCFt⊊PSCF.Proof.
AsPSCFtn contains the same equations and inequalities as PSCFt, but additionally Inequalities (3.22); thus we have PSCFtn⊆PSCFt. Figure 7 shows an LP solution of PSCFt that is not contained in PSCFtn, which implies PSCFtn⊊PSCFt. Such an LP solution may still contain fractional labels due to odd holes, as shown in Figure 5, by which we obtain PSCFtno⊊PSCFtn.
If the values of the edge and label variables in Figure7 are decreased as much as possible for SCF, we obtain la=1/4,lb=38, and lc=1/8 implying flp=3/4. As SCFt contains the additional Inequality (3.5), we can conclude that PSCFt⊊PSCF.Figure 7
LP solution ofSCFt with objective value flp=1+5/8(la=1/4,lb=3/8,lc=1). The blue arcs depict the flow variables with their according LP-values. Corresponding values for the edge variables are also shown. This solution is not valid for SCFtn, as the sum over the set of labels adjacent to node v2 is smaller than one.Proposition 3.3.
(3.42)PDCuttno⊊PDCuttn⊊PDCutt⊊PDCut.Proof.
The proof ofPDCuttno⊊PDCuttn⊊PDCutt follows by the same reasoning as for the proof of Proposition 3.2. Figure 8 shows that PDCuttn⊊PDCutt. However, the requirement that each directed cut must have a value greater than one already implies that ∑e∈δ(v)xe≥1,  for all v∈V. This implies ∑e∈Exe≥|V|-1. An LP-solution to DCut may contain more edges than an LP-solution to DCutt, which does, however, due to the minimality not affecting the objective value of the LP-relaxation, that is, PzDCutt=PzDCut.Figure 8
LP solution ofDCutt with objective value flp=(2+1)/6(lb=1/2,lc=2/3,la+ld+le≥1,w.l.o.g.la=1). The green arcs depict the arc variables with their according LP values. The solution is not valid for DCuttn, as the sum over the set of labels adjacent to node v5 is smaller than one.LetPS denote the projection of some polyhedron P to a subspace S.Proposition 3.4.
(3.43)PxECtno⊊PxECtn⊊PxECt⊊PxEC.Proof.
By applying the same reasoning as for the proofs of the last two theorems, we can prove Proposition3.4. Figure 9 gives an example for PECtn⊈PECt.Figure 9
LP solution ofECt with objective value flp=3/2+ϵ(la=ϵ,lb=1/2,lc=1). The solution is not valid for ECtn, as the sum over the set of labels adjacent to nodes v1 and v2 are smaller than one.In the following we will show the relations between the formulationsSCFt, DCutt and ECt.Theorem 3.5.
(3.44)PxDCutt⊊PxSCFt⊊PxECt.Proof.
Figures8, 7, and 9 already showed that the polyhedrons are not equal. To prove that PxDCutt⊊PxSCFt, we show a procedure to transform all x-variables of any valid LP-solution of DCutt to a valid x-solution in SCFt. For all i,j∈V, there exists at least one path from i to j with all edges (k,l) having LP-values xkllp greater than zero. If we consider a network with source i and target j, only containing edges e being part of one of these paths and having capacities xelp there exists a flow of at least one unit from s to t. We now arbitrarily select a root node r (w.l.o.g. r=0) and show how to construct a valid flow permitting the same x-configuration for SCFt as in DCutt. For an edge e to have LP value xelp, a corresponding flow variable must be larger than xelp/(n-1). We start by setting all flow variables to zero. Then, for each node ti,i=1,…,n-1 we construct all paths from r to ti, considering all edges with xelp>0. Summing up xelp>0 for all edges e on these paths may not exceed n-1, as the number of edges is fixed by (3.5) when i=2. However, this sum may usually be smaller than n-1, say λl, but integer. Now, we backtrack all these paths and set their flow values to minimal values according to flow conservation (3.7) and LP-values for the edges. Note that ∑i∈δ(r)fri=λ1 after this first step. We then continue this procedure for all further ti,i=2,…,n-1. According to (3.5) in step tk at most (n-1)-∑l<kλk not yet considered edges need to be added, possibly increasing ∑i∈δ(r)fri by exactly this amount. We finally end up with all nodes being feasibly connected and ∑i∈δ(r)fri=(n-1) fulfilling (3.6) and flow conservation (3.7) being fulfilled at each node.
It is trivial to see that thex-variables of a valid LP-solution of SCFt are also valid for ECt.Theorem 3.6.
(3.45)PxDCuttn⊊PxSCFtn⊊PxECtn.Proof.
In the proof of Theorem3.5, we already showed how each projection of a solution of DCutt to the subspace defined by the x-variables can be transformed into a solution of SCFt, and likewise SCFt to ECt. The only difference of the polyhedrons considered in Theorem 3.6 are the constraints (3.22), which clearly do not affect this transformation. It needs to be shown that the polyhedrons are not equal, which is done by the example in Figure 10. The depicted ECtn solution is not valid for SCFtn or DCutn, respectively, although the node-label constraints (3.22) are fulfilled. However, the value of edge {3,4} can be increased to 1/5 (implying the need to decrease the values of edges {1,4} and {3,6} accordingly), which makes the solution feasible to SCFtn. Nevertheless, this solution remains infeasible to DCuttn, by which we have shown the theorem.Figure 10
Valid LP-solution ofECtn with flp=2+ϵ(la=1,lb=ϵ,lc=1) that is not valid for SCFtn. It can however be transformed to such, by increasing x3,4 to 1/5, yielding flp=2+1/5. It is easy to see, that this solution is still not valid for DCuttn.


## 4. Results

In this section we present a comprehensive computational comparison of the presented formulations and separation strategies, and compare our methods to other work. Three different data sets are used for our computational tests. We start by a description of the test instances used for our experiments and tests.


### 4.1. Test Instances

The first set is the publicly available benchmark set used in [6, 10, 12, 13]. We refer to this data set as Set-I. It consists of graphs with 100 to 500 nodes and various densities d∈{0.2,0.5,0.8}, defined by |E|=d·(|V|·(|V|-1)/2), and different numbers of labels |L|=l/4,l∈{1,2,4,5}. The instances are organized in groups of ten for each configuration of d and |L| for each |V|. So far, primarily metaheuristics have been applied to this instance set, but also an exact algorithm based on A*-search, as reported in [12].The second test setSet-II is created following the specification of the instances used in [16], in order to obtain comparable results to the MIPs presented therein. This set is organized in four groups. In contrast to SET-I, the instances of the first two groups just contain very few labels, that is, |L|∈{5,10,20}. The number of nodes ranges from 20 to 1000, and network densities are set to |E|=4·|V|. Moreover, this set contains various grid-graphs (group 3) of sizes 2×10, 4×5, 2×18, 3×12, and 6×6. The fourth group contains instances with |V|∈{20,50} and |L|=|V| and various network densities d∈{0.2,0.5,0.8}.In addition to SET-I and SET-II we created a further test setSet-III containing also instances with multiple labels assigned to the edges. The construction is performed by first creating a spanning tree and assigning labels from set L*⊆L to its edges. Usually L*=L if not stated otherwise, but |L*|≪|L| is used to study the effect of having optimal solutions with significantly less labels than for completely random label assignment for the particular graph properties. Next further edges are added until a specified density d·(n·(n-1))/2,0<d≤1 or specified number of edges m∶=|E| is reached. Then, we randomly assign all labels not used yet. In the final step we iterate over all edges and assign further labels by uniform random decision. Parameter a specifies how many labels can be assigned to each edge, if not stated otherwise a=1. Instead of directly using |L| as a parameter, we may also specify the size of the label set by parameter r=|L|/|E|,0<r≤1. In contrast to the other instances, the instances of SET-III have relatively high values of r, that is, r=1/4 and r=3/4. Although such instances are less likely to occur within practical applications regarding telecommunication network design, they may be relevant for other scenarios, as for instance the compression model based on the MLST problem presented in [17].


### 4.2. Test Environment

The generic framework presented in Section3 has been implemented in C++ (gpp-4.3) within the SCIP framework [26]. The standard plugins have been used for all computational tests unless explicitly stated otherwise. In addition some branch-and-cut algorithms (not involving any pricing procedures) have been implemented within the ILOG CONCERT framework [27] for comparison purposes. As LP solver ILOG CPLEX (in version 12.0) [27] has been used for both frameworks.All computational tests have been performed on an Intel Xeon E5540 processor operating at 2.53 GHz and having 24 GB for total 8 cores. The operation system is Ubuntu 9.10 with Linux-kernel 2.6.31. All runs have been performed in single-threaded mode, CPU times have been limited to 7200 seconds, unless stated otherwise.


### 4.3. Comparison of Described Methods

In this section, we present a comparison of the described formulations based on computational tests. Furthermore, we analyze the impact of particular “components” to each of the formulations. These components consist of the node-label-inequalities (3.22), the extended node-label-inequalities (3.23), the strong linkage of the edges to the edges (3.21), which can, however, only be used if only one label is assigned to the edges and the number of edges is not fixed by (3.5). Table 1 provides an overview of these components and corresponding notation. After the comprehensive analysis and comparison of the particular methods in this section, we compare the results of the newly proposed methods to previous work in Section 4.4.


#### 4.3.1. MIP Formulations

In this section, we primarily focus on the comparison of formulations EC, DCut and SCF. However, particularities like node-label-constraints (3.22), or fixed number of edges (3.5), or the direct linkage of labels to edges (3.21), may significantly change the picture regarding the superiority of one method over another one. For this reason, we present the results not only for three formulations, but rather four to five variants of each formulation. Recall, that directly linking the labels to edges by (3.21) is only possible for instances with one label assigned to each edge (3.21), that is, a=1 and is generally not possible for flow-formulations. In order not to be biased towards some particular class of instances, we report these results for each of the three instance sets.Tables2 and 3 show the results for instances of SET-I with |V|=100 and |V|=200. These instances include graphs with various densities d∈{0.2,0.5,0.8}, where |E|=d·(|V|·(|V|-1)/2), and different numbers of labels, that is, |L|=1/2·|V|,|L|=|V|, and |L|=5/4·|V|. In these tables, as well as in the following ones, we report the following entities for each method and group of instances.  Columns “cnt” contain the number of instances within each group, which is 10 in most of the cases. The reason for less than ten instances reported is not being able to finish some instances with particular formulations due to high memory requirements. Columns “opt” report the number of instances that have been solved and proved to be optimal within the time limit. In columns “obj” the average objective value for all instances in the group is reported. If all instances have not been solved to optimality, this value corresponds to the average value of feasible solutions that have been found within the timelimit. Average running times in seconds are then reported in columns “t”. The average number of branch-and-bound nodes is listed in columns “bbn”, the average number of generated cuts in column “cuts”. Results of the fastest method(s) for each group are emphasized with bold letters.Table 2
Comparison of selected variants of formulations EC, DCut, and SCF on the instances from SET-I with|V|=100.
|L|=50|L|=100|L|=125dalgcntoptobjtbbncutscntoptobjtbbncutscntoptobjtbbncuts0.2EC10106.772346510109.762387610729911.212393652843ECt10106.7834719610109.72524824149911.2343769871ECtn10106.7410017310109.7118573399911.2161401402ECn10106.7024310109.7912981799911.2332648594ECsn10106.7031310109.761127349911.212257089DCut10106.780116769110109.710131437877989811.214701964611403DCutt10106.7125145895410109.7478667639199911.2740102736450DCuttn10106.72112711610109.78610217299911.211514261017DCutn10106.711909610109.75711575999911.217631861868DCutsn10106.712948910109.75111905169911.212930861536SCF1026.87028136930−110010.3720019854−19012.4720017296−1SCFt1016.77133143226−110010.37200101319−19011.77200119683−1SCFtn10106.71583−110109.767673−19911.2851033−1SCFn10106.71583−110109.763673−19911.2841033−10.5EC10103.01746510104.7374558428210105.24465307630ECt10103.0146914810104.7175503933010105.21293249382ECtn10103.09713610104.73452416510105.239452277ECn10103.002010104.78221410105.291274ECsn10103.002010104.79173410105.21137012DCut10103.02174882721084.8385815810721410105.2315093164187DCutt10103.01904652561094.7347111770624610105.2179453663175DCuttn10103.056132810104.7401113345010105.2305633342DCutn10103.027122810104.7261159751810105.22501179401DCutsn10103.027235510104.7216153939010105.22251234362SCF10103.08501475−11005.0720011453−11005.872007586−1SCFt10103.07221597−11064.7531923618−11005.5720018169−1SCFtn10103.0221−110104.7211617−110105.2171298−1SCFn10103.0201−110104.7203617−110105.2176298−10.8EC10102.01221210103.01618489810104.0999431020ECt10102.011719610103.03614217910104.01352344130ECtn10102.014410210103.0241118710104.04439483ECn10102.001010103.013210104.0171020ECsn10102.001010103.024110104.017510DCut10102.025597651093.12367244012861004.0720069583525DCutt10102.01981271311093.11997270216351094.0508363633410DCuttn10102.08771910103.031437021610104.09231193408DCutn10102.04052210103.041893245710104.07801853546DCutsn10102.03332910103.01281619310104.07402154668SCF10102.0274103−11003.672002826−11004.072002752−1SCFt10102.0335−11004.072003035−11004.072002849−1SCFtn10102.0281−110103.0292−110104.0243349−1SCFn10102.0281−110103.0292−110104.0230349−1Table 3
Comparison of selected variants of formulations EC, DCut, and SCF on the instances from SET-I with|V|=200.
|L|=100|L|=200|L|=250dalgcntoptobjtbbncutscntoptobjtbbncutscntoptobjtbbncuts0.2EC1088.03770526821662110012.97200422892230310015.472003200918669ECt1078.0454143756766510013.6720043298800710016.07200437927293ECtn10107.912961425453910213.3687860643143610114.96761462961658ECn10107.92018379510512.2514618903397310313.863871445975207ECsn10107.91918322410712.143311822378110313.96153250129158DCut1008.8720010929897110014.572003850363210018.9720036813548DCutt1009.072004392403610014.572002896286610016.1720026532622DCuttn1078.1548713056803610013.072005588476310015.7720039823552DCutn1098.0339814653863710012.97200158771220010014.97200112079494DCutsn1098.0299614937765810012.77200192801356910014.772001371210837SCF1009.372001017−110014.57200634−110016.87200559−1SCFt1008.972003204−110013.572004733−110015.872005326−1SCFtn1088.033539362−110012.472006854−110014.172004343−1SCFn1088.034988308−110012.472006468−110014.172004099−10.5EC10103.47692082691005.8720086035391006.572005380456ECt10103.4145227445581005.87200103076471006.4720090841024ECtn10103.45704696781075.5424965509081006.5720015870861ECn10103.42512611095.4129114284121086.443235771531ECsn10103.4199211095.411761465361096.440496237118DCut904.1720010867281007.272003232651007.97200272215DCutt904.372006134691007.972002982901008.27200335307DCuttn1083.551359544811006.672005573491007.47200420282DCutn1083.5313210795071006.2720017959291007.172001097564DCutsn1093.420549794121006.0720020729121006.772001432671SCF1004.37200124−11007.0720069−11007.8720054−1SCFt1003.97200207−11006.57200166−11007.37200150−1SCFtn10103.41102270−11005.77200828−11006.57200839−1SCFn10103.41204270−11005.77200749−11006.47200728−10.8EC10102.628032968161004.072001132161005.07200164048ECt10102.6304036505051004.0720021466561024.470646763757ECtn1092.7273910361310104.0503868196341094.129021331776ECn10102.67627310104.011225975110104.060933243ECsn10102.6281110104.09114845110104.03017771DCut403.072001521341008.272011051101007.172006970DCutt1003.972001511711005.272021101121006.87200111112DCuttn1033.36344142671004.672001771021005.5720012098DCutn1032.7652811034441004.272003291701004.97200158126DCutsn1062.651357992921004.072005562271005.07200226140SCF1002.9720069−11004.9720035−11005.5720033−1SCFt1022.8592354−11004.3720058−11005.1720135−1SCFtn1092.6417774−11014.06929391−11034.76712264−1SCFn1092.6418379−11014.06973375−11024.76871229−1From Tables2 and 3 we can already observe that the difficulty of solving these instances is strongly correlated to the objective function values of the instances. Higher values, in particular those larger than ten, require significantly more B&B-nodes, and the separation of more cuts. This also implies longer average running times. This property holds for all of the considered formulations. The results in Tables 2 and 3 show that formulation ECsn consistently gives the best results for these instances. The single-commodity flow formulations show a slightly better performance than the directed-cut formulations for most of the instances.The strength of the node-label-inequalities (3.22) is also demonstrated by the results in Tables 2 and 3. Their addition to the plain formulations does not only yield a significant speedup, but also enables to solve more instances regarding the set with |V|=200. The difference between Inequalities (3.22) and their extended form, given by Inequalities (3.23) is examined in Section 4.3.2. Regarding Equation (3.5) no clear conclusion can be drawn from these instances. If, however, combinations of these components are considered, the variants only using the node-label-constraints are superior in most of the cases. For formulations EC and DCut it is also possible to directly link the edges to the labels by   (3.21). In most of the cases, this yields the best results, when combined with the node-label-inequalities for both formulations, and in particular in combination with EC the overall best results.Table4 reports the results for the same formulations for the instances of SET-II. These instances have the major difference to contain only graphs of extremely low density d and just very few labels. Again, we can observe a clear superiority of formulations ECsn and ECn, which are able to solve all these instances with average running times of less than  half second.Table 4
Comparison of selected variants of formulations EC, DCut and SCF on the instances from SET-II.
|L|=5|L|=10|L|=20|V|, |E|algcntoptobjtbbncutscntoptobjtbbncutscntoptobjtbbncuts200,  800EC10103.001010105.003010107.90132ECt10103.00223610105.00831510107.9247582ECtn10103.00215710105.00624910107.9120515ECn10103.001010105.001010107.9062ECsn10103.001010105.001010107.9061DCut10103.0163810105.04146310107.914127171DCutt10103.0362610105.07183710107.918161173DCuttn10103.0042910105.0273610107.982163DCutn10103.0022410105.0064910105.00649DCutsn10103.001010105.001010107.9061SCF10103.022−110105.0932−110107.969800−1SCFt10103.032−110105.0932−110107.971800−1SCFtn10103.001−110105.013−110107.9616−1SCFn10103.001−110105.013−110107.9616−1500,  2000EC10103.501010105.902010109.90120ECt10103.53262110105.96783310109.916441129ECtn10103.52154110105.95676310109.916251385ECn10103.501010105.901010109.9080ECsn10103.501010103.501010109.9070DCut10103.5553410105.914147610109.948152184DCutt10103.51372510105.928153410109.968181144DCuttn10103.5231610105.9983310105.99833DCutn10103.5124610105.9366710109.92020139DCutsn10103.5128210105.9366010109.92019129SCF10103.5103−110105.92818−110109.9372661−1SCFt10103.5113−110105.92918−110109.9384661−1SCFtn10103.501−110105.943−110109.92020−1SCFn10103.501−110105.933−110109.91820−11000,   4000EC10104.101010106.6010101011.30130ECt10104.1201118210106.64661762101011.3121543514ECtn10104.13001382310106.623462660101011.3108262909ECn10104.101010106.6010101011.3070ECsn10104.101010106.6010101011.3060DCut10104.11654010106.64713259101011.3144191275DCutt10104.15462210106.6902036101011.3240189150DCuttn10104.1732310106.626726101011.31033647DCutn10104.112118410106.6135195101011.36426355DCutsn10104.111117810106.6476495101011.35724253SCF10104.1302−110106.69914−1101011.31243416−1SCFt10104.1312−110106.69614−1101011.31303416−1SCFtn10104.111−110106.6123−1101011.35231−1SCFn10104.111−110106.6123−1101011.34831−1In Tables5, 6, and 7, results for the instances from SET-III are reported. Table 5 shows the results for instances with |V|=100 and a=1, that is, one single label assigned to the edges. As already mentioned in Section 4.1, this instances differ from the previous ones in the way that they contain a higher number of labels, that is, r=1/4 and r=3/4 with r=|L|/|E|. It can be observed that it is beneficial to limit the number of edges to |V|-1 by (3.5) in this case. Thus, the stronger LP-relaxation implied by this restriction is beneficial in the case of higher values of r. For instances with r=1/4 formulation EC still shows the best performance, but DCut provides better results in the case of r=3/4. Hence, the strong LP-relaxation becomes even more important if |L| is in the same order of magnitude as |E|.Table 5
Comparison of selected variants of formulations EC, DCut and SCF on the instances from SET-III with|V|=100; α=1.
|L|=1/4·|E||L|=3/4·|E|dalgcntoptobjtbbncutscntoptobjtbbncuts0.05EC101019.621892172210061.67200108393124719ECt101019.6236887602610151.36480178187195559ECtn101019.6144944448610251.25760163875182801ECn101019.621491124610062.57200103413119245ECsn101019.61131396610055.57200133833151889DCut101019.6355214302610050.77200367146337417DCutt101019.6344174248710449.843817662955867DCuttn101019.612114875910649.831958715260318DCutn101019.613143794110050.47200337882315950DCutsn101019.61131396610050.47200360801343056SCF10319.65576987720−110051.572001815207−1SCFt10919.61354513872−110550.038233081605−1SCFtn101019.6315160−110849.91508800971−1SCFn101019.6499415−110050.67200894051−10.2EC10115.1709920808211736210045.172006230063102ECt101014.8675547422379010436.56326138547137549ECtn101014.8344363861674510237.16450120465121687ECn10215.363691366579492710046.072004016341557ECsn10414.848942311489506210039.272006516763256DCut10016.37200480733531610038.9720011978987861DCutt10614.83196551693714410635.837066176247626DCuttn101014.883513677869810735.824323609927852DCutn10015.77200391322970010038.572004857640239DCutsn10115.67134783395754610038.072008864573235SCF10017.0720014435−110040.5720039472−1SCFt10015.57200173479−110037.87200480980−1SCFtn10914.8240131073−110136.16495152260−1SCFn10015.2720063078−110038.4720029479−10.5EC10015.87200695543626010038.872005415355751ECt10813.32570624873042510530.740645144250552ECtn9813.21400341061876910431.050385960557375ECn10016.27200359441832310038.972002898431127ECsn10013.772002967828896210033.872006343064801DCut10015.472007645429110036.072003100819324DCutt10613.551529463903610630.343311600313285DCuttn10513.545579195854310730.23552123379780DCutn10015.472005807378510036.6720069355131DCutsn10014.4720012834815410032.47200141089913SCF10016.472001345−110034.572003160−1SCFt10014.6720019313−110032.3720035869−1SCFtn10513.547569842−110230.7584216960−1SCFn10014.572006765−110033.172002327−1Table 6
Comparison of selected variants of formulations EC, DCut and SCF on the instances from SET-III with|V|=100, a∈{2,5}.
|L|=1/4·|E|,a=2|L|=3/4·|E|,a=2|L|=1/4·|E|,a=5|L|=3/4·|E|,a=5dalgcntoptobjtbbncutscntoptobjtbbncutscntoptobjtbbncutscntoptobjtbbncuts0.05EC101016.673222327710042.87200112158123363101010.5015245210021.47200111275106501ECt101016.66311657990110735.02558113102106934101010.5036240010420.84763178547160611ECtn101016.6124707408010735.0237510217993532101010.5030635910620.63467143690125295ECn101016.621883195610042.47200116472124838101010.5015842610021.57200107718103093DCut101016.6314173240910035.17200374197286064101010.5724723810020.57200375009236293DCutt101016.63635232114101034.711267254842101010.51035030110920.510667558746230DCuttn101016.6161162787101034.76146613696101010.55115134101020.56984587025073DCutn101016.611102669410035.07200376389268567101010.539511510720.54126215290129837SCF10116.77153896512−110037.17200701281−110910.52318507224−110021.87200276624−1SCFt10716.640381339695−110135.070463581766−1101010.51580440888−110021.072001707957−1SCFtn101016.6293894−1101034.7609239014−1101010.54284−110920.52218462195−1SCFn101016.66711755−110035.87200666248−1101010.55329−110020.97200720521−10.2EC10312.3652126824011707910031.87200727206934510107.833642365853498710019.57200159231107082ECt10812.11840815984010910326.2584514156812722910107.82653987577310315.1518417149089976ECtn101011.9629420522063710326.3524211955010735810107.81281244165110315.1514013998390176ECn10712.142851660547945710034.07200498595094010107.8104156147816610019.0720011518889434DCut10013.47200434123249710027.3720072779487721017.96892706903650710016.672003335023851DCutt101011.91477178411318310725.6295755433381211057.85653677544256010414.954235580043216DCuttn101011.96815906518010925.61489249311766310107.8162815222955210614.844064462832312DCutn10013.27200395993022510027.4720031085234201077.84679654152581210015.872001576111375SCF10014.3720013282−110030.0720019389−11008.8720022933−110018.1720012399−1SCFt10012.97200105555−110027.07200320786−11008.17200107916−110015.87200109149−1SCFtn10812.1190918528−110425.9533887496−110107.8166911756−110215.1632744397−1SCFn10012.8720047542−110027.6720015439−11097.8415159801−110016.0720010494−10.5EC10011.57200982573800010028.4720093989774941016.96785101172724210014.572005051829040ECt101010.963242951526810123.46487854857100310106.9612279367859513.1380410066638284ECtn101010.950622467643210326.3524211955010735810106.925566045329613.034727258238165ECn10011.37200378581836510029.0720044406399261007.0720029141214310016.27200117516165DCut10011.872009769550310030.472001585295161007.1720011487599510015.2720057423186DCutt10011.37200130891156010822.54745958588511007.472007977621310013.8720078277958DCuttn10511.2566411813978610522.84259885084811067.150895318352910413.1574379347389DCutn10011.972007129442610027.17200473829961017.167177337317210015.2720026821652SCF10013.272001477−110026.872001628−11008.072002606−110016.27200923−1SCFt10012.1720013970−110024.3720026439−11007.672006757−110014.3720010634−1SCFtn10610.948416975−110023.4720012529−11077.042383003−110213.359236203−1SCFn10011.872009232−110025.072003000−11007.0720021470−110014.472004668−1Table 7
Comparison of selected variants of formulations EC, DCut and SCF on the grid graph instances from SET-III with|E|≈4·|V|.
|V|=10×10|V|=20×20|L|algcntoptobjtbbncutscntoptobjtbbncuts30EC10109.2420411540101011.5617496400ECt10109.2626411843101011.518375475819ECtn10109.2416391544101011.59137574231ECn10109.211369656101011.5173602200ECsn10109.211281601101011.5173558175DCut10109.261494832402211.05224623337505DCutt10109.29361964135101011.530292295619238DCuttn10109.23418921710101011.5627405810961DCutn10109.218151213641012.072003924766DCutsn10109.219135623141013.072002623113SCF10109.2815118270−110011.8720022192−1SCFt10109.264190448−110011.7720022091−1SCFtn10109.2171280−1101011.52513127−1SCFn10109.2121008−1101011.52183076−150EC9813.01018546534103610917.1434146460231132ECt9713.11959993977368710017.07200301858167539ECtn9813.015788399667834101017.03834212265107170ECn9912.91292529916378101017.0134720822111217ECsn9912.9662233913131101017.010871932138470DCut9912.986767360378737017.372002939047832DCutt9912.91032747184208810017.272003224833668DCuttn9912.9302205961290710017.072008617264236DCutn9912.933628974176137016.37200334536785DCutsn9912.920720951133237015.7720064823682SCF9013.37200368322−110018.5720013103−1SCFt9013.27200741954−110018.5720019592−1SCFtn9912.921521632−110017.17200131296−1SCFn9912.929934004−110817.15532169723−180EC10019.5720013460811837710025.07200199143139246ECt10019.9720023178920866110024.97200143214104486ECtn10019.6720022961920278710024.87200146616112030ECn10019.5720016219213890410024.67200305748138953ECsn10018.9720022816717674110024.67200299188134344DCut10018.8720025282622527310025.572003175632402DCutt10018.972002481232165139019.872002412125391DCuttn9018.7720028362522094010025.272004360444755DCutn10018.872002394891970738024.672005422662124DCutsn10018.972002489662131577025.172002526246754SCF10019.77200285092−110027.072009767−1SCFt10019.27200948572−110028.0720022180−1SCFtn10019.07200689593−110025.3720068435−1SCFn10018.87200863039−110025.2720099643−1With a single exception, the same effect can be observed for the instances witha∈{2,5} reported in Table 6. The effect of more than one label being assigned to the edges seems to make the problem easier to solve, but the effect is relatively small. It is important to note, that directly linking the labels to the edges, which was beneficial for the instances with a=1, cannot be applied to instances with larger a.Table7 shows the result for grid-graphs with 100 and 400 nodes and |L|∈{30,50,80}. The average optimal objective value on these graphs is relatively high, which makes them difficult to solve. However, all instances with |L|∈{30,50} could be solved to optimality by formulation ECsn, which showed the overall best performance on this class of instances.Having now analyzed the main variations of the discussed formulations we draw our attention to further approaches and enhancements that have been proposed in Section3.


#### 4.3.2. Further Methods

In Section4.3.1 the node-label-inequalities (3.22) have been shown to be of utter importance for a strong formulation. In Section 3.3 we have also presented an extension of this idea, where two nodes are considered instead of just one. This led to the class of Inequalities (3.23). Table 8 shows a comparison of formulations ECt and DCutt with on the one hand the node-label-inequalities (3.22) and on the other hand additional Inequalities (3.23). In particular for formulation ECt these further inequalities turn out to be useful in many cases. They do not only speedup the solution process, but moreover frequently enable to solve more instances to provable optimality. However, also the opposite is often the case. It is therefore not possible to decide which approach is superior over the other based on the available data. On grid-graphs Inequalities (3.23) have not been beneficial at all.Table 8
Comparison of formulationsECt and DCutt with Inequalities (3.22), indicated with index n, and with additional Inequalities (3.23), indicated with index ñ.
ECtn/DCuttnECtñ/DCuttñ|V|,|E|,a,|L|cntoptobjtbbncutscntoptobjtbbncuts100,247,1,61101019.61449444486101019.60499492101019.6121148759101019.61915771034100,247,1,18510251.2576016387518280110750.02174657816872310649.83195871526031810549.842848676962183100,900,1,247101014.83443638616745101014.8177183526741101014.8835136778698101014.819492697316494100,900,1,74210237.1645012046512168710735.82403480384539810735.82432360992785210835.718222052215153100,2475,1,61810813.2140034106187699813.21801464692236310513.545579195854310413.65417107739933100,2475,1,185610431.05038596055737510730.32506272412495710730.2355212337978010830.2290737153689100,247,2,61101016.61247074080101016.61601498101016.6161162787101016.6211348907100,247,2,18510735.0237510217993532101034.7932693274101034.76146613696101034.71914251226100,900,2,247101011.96294205220637101011.99125510620864101011.968159065180101011.915231643512011100,900,2,74210326.3524211955010735810725.83265696855378510925.61489249311766310925.615831707612240100,2475,2,618101010.9506224676432101010.955837153392110511.2566411813978610111.770501250311444100,2475,2,185610423.25213619085329410323.25757731455765710522.842598850848110822.5364941854254100,247,5,61101010.50306359101010.50248306101010.55115134101010.511316321100,247,5,18510620.6346714369012529510920.512026057149983101020.56984587025073101020.54983677420977100,900,5,24710107.81281244165110107.82883932482510107.816281522295521057.856756649942125100,900,5,74210315.15140139983901769415.043441555897319810614.84406446283231210414.951715043438692100,2475,5,61810106.9255660453210106.9624279367851067.15089531835291007.4720083036431100,2475,5,185610613.03472725823816510613.038481036354165110413.157437934738910113.671918419861710×10,360,1,3010109.241639154410109.262641184310109.2341892171010109.2906196413510×10,360,1,509813.0157883996678349813.01877102421756929912.930220596129079912.91034747184208810×10,360,1,8010019.6720022961920278710019.9720025195722694110018.772002836252209409018.8720028328824139920×20,1520,1,30101011.59137574231101011.517675475819101011.5627405810961101011.52866229561923820×20,1520,1,50101017.0383421226510717010117.0719432605117805810017.07200861726423610017.27200347423577920×20,1520,1,8010024.8720014661611203010024.9720015052911012010025.27200436044475510020.672002571826997Further formulations, considered in Section3, are based on the property that a tree must not contain a cycle by definition. Formulation MTZtn requires just a polynomial number of variables, but contains constraints with infamous “Big-M” constants, as the SCF formulation does. On the contrary CEF contains an exponential number of Inequalities (3.15), which need to be separated as cutting-planes as for the DCut or EC formulation. Due to their fast separation by a simple shortest-path computation, other formulations may benefit from additionally using cycle-elimination cuts. Corresponding results are reported in Table 9, column “cec” lists the average number of separated cycle-elimination cuts. Whereas MTZtn and CEFtn show a relatively weak performance on the instances with r=1/4, they provide good results in the case of r=3/4. In particular, for the low-density graphs CEFtn could solve all instances to optimality, which no other method was able to do. For the dense graphs best results are obtained by DCuttnc and ECtnc.Table 9
Comparison of various formulations based on cycle elimination, that is, the Miller-Tucker-Zemlin formulation MTZ and the CEF on the instances from SET-III with|V|=100, a=1. Furthermore results for connectivity-based formulations (EC and DCut), enhanced by cycle elimination inequalities are reported.
|L|=1/4·|E||L|=3/4·|E|dalgcntoptobjtbbncutsceccntoptobjtbbncutscec0.05MTZtn10519.73931502063−1−110749.93112721279−1−1CEFtn10619.63000135407−116638101049.890194205−16389CEFtñ10519.63998155632−11764210749.92208208113−114321ECnc101019.61413531215910050.372005328361707981783ECtnc101019.6129151539610749.8256662656446075502DCutnc101019.61314339315510050.472003766493512881630DCuttnc101019.61310297009410749.82291367452774828590.2MTZtn10715.0427645276−1−110535.8427287003−1−1CEFtn10714.9321736913−1329810735.7231391215−15422CEFtñ10315.2530761399−1569010735.7266840566−12478ECnc10015.672003183514311810037.8720059337153330ECtnc101014.87011068719667010835.7187151079155443426DCutnc10015.97200392252975517110039.4720047294392063DCuttnc101014.873711214721258110835.71537217211379514000.5MTZtn10513.555557818−1−110330.9565813851−1−1CEFtn10513.650388686−176310730.1444419156−11653CEFtñ10313.657918399−1106310530.555706646−1711ECnc10014.172003463263510032.77200649711825ECtnc10713.53865877211691310930.1211291201344665DCutnc10015.67200535333952410038.27200696453576DCuttnc10813.533947452643367510930.0242774755918576Table10 shows the results that have been obtained by including primal heuristics into the branch-and-bound algorithm. Formulations ECtn, ECsn, DCuttn, and DCutsn are considered for this purpose. As indicated by preliminary experiments it turned out to be advantageous only to use the primal heuristics in the root node, as they were generally not able to find improved solutions based on the information provided by the LP-solution in other B&B-nodes. Embedding MVCA in B&B has a positive effect w.r.t. the variants “tn” of formulations EC and DCut, but a negative impact concerning variants “ts”.Table 10
Comparison of best formulations used without and with primal heuristics, that is, MVCA and ACO.
|L|=1/4·|E||L|=3/4·|E|dalgcntoptobjtbbncutscntoptobjtbbncutsECtn101019.6144944448610251.257601638751828010.05ECsn101019.61131396610055.57200133833151889DCuttn101019.612114875910649.831958715260318DCutsn101019.610133689510649.831958715260318ECtn+MVCA101019.6125474486610251.35771145352166307ECsn+MVCA101019.621635125510052.37200137776154933DCuttn+MVCA101019.611105671410649.829025728241009DCutsn+MVCA101019.612153099310050.47200371927343330ECtn+ACO101019.612442539168449.63600107155110775ECsn+ACO101019.62133997810049.97200134930151941DCuttn+ACO101019.6109376279449.840197450652846DCutsn+ACO101019.611130382810050.47200371927343330ECtn101014.8344363861674510237.164501204651216870.2ECsn10414.848942311489506210039.272006516763256DCuttn101014.883513677869810735.824323609927852DCutsn101014.883513677869810038.072008864573235ECtn+MVCA101014.8767524962853110236.96004120042120862ECsn+MVCA10414.849042122228987310038.772006330860554DCuttn+MVCA101014.879912503828410835.721693421925835DCutsn+MVCA10115.57067726585489410038.172008257567712ECtn+ACO101014.834531157143139536.041356736266292ECsn+ACO10314.953232282739441010036.172006434060405DCuttn+ACO101014.86401103471499635.825243556026632DCutsn+ACO10215.06977807255492510036.272008355369016ECtn9813.21400341061876910431.0503859605573750.5ECsn10013.772002967828896210033.872006343064801DCuttn10513.545579195854310730.23552123379780DCutsn10014.4720012834815410730.23552123379780ECtn+MVCA10813.31991404402399510530.542745320250948ECsn+MVCA10013.772002798957963310032.472006702666888DCuttn+MVCA10713.333216462585210930.0272884797236DCutsn+MVCA10014.3720011154722410032.272001487810082ECtn+ACO9713.3226144962257186231.354196148159297ECsn+ACO10013.772003453588005410031.172006446963099DCuttn+ACO10713.43534765969338530.53374105778304DCutsn+ACO10013.8720012035731910031.27200139199175


#### 4.3.3. Odd hole Inequalities

We now draw our attention to the odd hole inequalities. Within preliminary tests, we determined a tight timelimit of 10−3 seconds for solving the MIP (3.26)–(3.38) to show a generally good performance. Two algorithmic variants are considered for the results reported in Table 11. The first version (denoted with index o) simply adds the found valid cutting-planes to the MIP. Alternatively, the set of labels corresponding to the obtained odd hole can also be used to deduce a branching rule. This was motivated by the observation that many lifted odd hole cutting planes, found by MIP (3.26)–(3.38), were not strong enough to define facets w.r.t. the involved label variables. As a consequence, these variables remained fractional after the cutting-plane was added to the MIP. However, odd holes provide important information and references to situations where special configurations of label-variables artificially reduce the LP-relaxation. Hence it is likely that immediately branching over these variables may be beneficial. This is done by inserting all labels of the odd hole into a global queue, and always branch over such a variable unless the queue is empty. Index ob denotes this approach in Table 11. Odd hole cuts are separated with lowest priority amongst the user-defined cutting-planes, and are only separated in levels of the B&B-tree which are multiples of ten.Table 11
Comparison of formulationsECt and DCutt with and without using odd hole ienqualities. Index o denotes if odd hole inequalities are separated, index b indicates that odd hole inequalities have been used to induce branching over related label variables.
ECtn/DCuttnECtno/DCuttnoECtnob/DCuttnob|V|,|E|,a,|L|cntoptobjtbbncutsoptobjtbbncutsohoptobjtbbncutsoh100,247,1,61101019.614494444861019.62556925141231019.6175226470119101019.61211487591019.613116377211019.61311217331100,247,1,18510251.25760163875182801251.25760144151159964194251.1576014356215932117310649.831958715260318649.83214833475832211649.83197859976058513100,900,1,247101014.834436386167451014.841737993182841341014.83433463915817120101014.88351367786981014.889214659936411014.898715816101312100,900,1,74210237.16450120465121687336.863771268191289241251236.76007119218119667130810735.824323609927852735.82369347172634877735.82371337572608361100,2475,1,61810813.214003410618769813.324994859928883174813.31820354792177513810513.5455791958543713.54261830576159713.34318832277698100,2475,1,185610431.050385960557375530.841335307952191709431.04499549455425461410730.23552123379780930.028278780680951930.027788061689839100,247,2,61101016.612470740801016.61451484496231016.6134987436320101016.61611627871016.617116178801016.61611467751100,247,2,18510735.0237510217993532635.13485137028125999272735.0243110259590520178101034.761466136961034.7695073408181034.722175816304100,900,2,247101011.96294205220637912.099748954228661371011.98574193321903129101011.9681590651801011.98918242686861011.910008936773411100,900,2,74210326.35242119550107358326.253951184831043411312426.3484110707294593122010925.614892493117663925.61603241121803182925.61443238371680167100,2475,2,618101010.95062246764321010.9748289179107441010.93881777036841410511.25664118139786511.257361095894677611.157271115593168100,2475,2,185610423.252136190853294123.864907452564822822223.56298722566205975410522.8425988508481722.636427480707322822.534797831717320100,247,5,61101010.503063591010.5030635911010.512673381101010.551151341010.5511513401010.551151340100,247,5,18510620.63467143690125295420.74461157779137051937620.63047116829103068673101020.56984587025073920.5787438832492112920.5783451442557510100,900,5,24710107.812812441651107.8134125216312107.815713710862310107.81628152229552107.815131507192221107.815401515393650100,900,5,74210315.1514013998390176415.0483813275683094702415.044581256657832765110614.844064462832312514.94520458183317222514.94392444353226718100,2475,5,61810106.92556604532106.925365815190106.9262670157701067.150895318352967.0509255033685067.05093544736080100,2475,5,185610613.034727258238165712.931326247333275255712.92343501062408715810413.1574379347389313.36505889684209313.1621382597770810×10,360,1,3010109.2416391544109.251427135010109.25142713841110109.23418921710109.232168515105109.23417111576610×10,360,1,509813.015788399667834813.015508111266089310912.961954900424881459912.93022059612907912.9387251421618023912.92981993812261810×10,360,1,8010019.67200229619202787019.872002119031868851086019.57200211561188812110210018.77200283625220940018.87200232626190432403019.0720022397018883238120×20,1520,1,30101011.591375742311011.51073749431001011.5106379942490101011.56274058109611011.575340281156701011.5705411211261020×20,1520,1,50101017.03834212265107170917.0423220992310575532917.043242100031073853910017.072008617264236017.0720077221606036017.072008045359244420×20,1520,1,8010024.87200146616112030024.87200133250102086626024.9720013164110147957710025.272004360444755025.27200392624170421025.27200394514295219The results in Table11 show that the odd hole inequalities are beneficial in many cases, in particular when used to deduce branching rules from the corresponding label-variables. For instances from SET-I and SET-II, almost no odd holes have been found with the described parameter settings. For dense graphs it is less likely to find odd holes that are violated by the current LP-solution, as each node is incident to many edges. Hence |L(v)| is in the same order of magnitude as |V| in the expected case. This implies many nonzero lifting coefficients in Inequalities (3.25), reducing the chance of finding a valid inequality that is actually violated by the current LP-solution. Hence, the separation of odd hole inequalities is most beneficial for sparse graphs. Also the number of labels compared to the number of edges has an impact on the efficiency of the odd hole separation. If the number of labels is relatively low, the expected label frequency νl will be high. This implies high values for the lifting coefficients γl, which in turn reduces the chance of finding violated odd hole inequalities. If, on the other hand, the number of edges is too high, odd holes are generally less likely to occur, as the sets L(v)∩L(u), for all v,u∈V can be expected to be very small or even empty.


#### 4.3.4. Branch-and-Cut-and-Price

Additionally, using the column generation approach within the B&C framework, that is, branch-and-cut-and-price (BCP) is only beneficial for a very special class of instances. For most of the instances almost all variables are priced in during the solution process. The computational overhead for solving the pricing problem and resolving the MIP implies significantly higher running times in this case. However, if the instances consist of a high number of labels, and have an optimal solution that is significantly lower than the average optimal solution value when assigning the labels to the edges randomly in the instance construction process, BCP shows a superior performance. To study this effect, special instances have been created containing single optima having a relatively low number of labels. The computational results for these instances are reported in Table12. In particular for the larger instances a clear superiority of the BCP approach w.r.t. the corresponding B&C algorithm can be observed. For this special class of instances, the percentage of created label variables is always less than 30% of the total number of labels (reported in column “priced”). Although the importance of such instances may be quite limited for many purposes, the instances used for the data compression approach presented in [17] exhibit comparable properties. For the data-compression application presented therein, the BCP approach is thus a valuable and important mean for exactly solving large instances.Table 12
Branch-and-cut-and-price results for a special class of instances containing many labels and isolated optima with a relatively low number of labels.
|V|,|E|,a,|L|Methodcntoptobjtbbncutspriced100, 247, 2, 61ECtn10105.00132−1DCuttn10105.0017−1ECtnp10105.0016414DCuttnp10105.0011317100, 247, 2, 185ECtn101010.0011−1DCuttn101010.0012−1ECtnp101010.001211DCuttnp101010.00137100, 900, 2, 247ECtn10105.00130−1DCuttn10105.01115−1ECtnp10105.0017229DCuttnp10105.0021928100, 900, 2, 742ECtn101010.001442−1DCuttn101010.081325−1ECtnp101010.0249732830DCuttnp101010.012324125100, 2475, 2, 618ECtn10105.01246−1DCuttn10105.019415−1ECtnp10105.0165127DCuttnp10105.01141926100, 2475, 2, 1856ECtn101010.021548−1DCuttn101010.0401123−1ECtnp101010.01023717424DCuttnp101010.036232616300, 22425, 2, 1856ECtn101010.02281273−1DCuttn101010.061716−1ECtnp101010.010512572DCuttnp101010.04591132300, 35880, 2, 8970ECtn966.738461600−1DCuttn988.94113117−1ECtnp9910.0880167414DCuttnp9910.0113112012300, 35880, 2, 26910ECtn101010.06271254−1DCuttn101010.02735110−1ECtnp101010.025912622DCuttnp101010.012121183


#### 4.3.5. Summary

In Table13, we finally report the best method for each group of instances from the three instance sets. For this purpose, variations including primal heuristic and using cycle-elimination cut separation are also considered. In the case a variant including a primal heuristic yields the best performance, we additionally report the best method not using primal heuristics. Formulations ECsn and ECsnh are the best formulations for almost all instances of SET-I, with the primal heuristic often yielding small improvements. The same is true for the instances of SET-II, where almost all variations of formulation EC are able to solve the considered instances in less than a second. For SET-III formulation DCut is superior for many instances with |L|=3/4·|E|, whereas EC is better for instances with |L|=1/4·|E|. In contrast to SET-I, it is beneficial to restrict the number of edges to |V|-1 as indicated with index “t”. Additionally separating cycle-elimination cuts frequently yields the overall best method, in particular for instances with |L|=3/4·|E|. Furthermore it can be observed that variants using separation of odd hole inequalities are frequently the overall best methods for this group.Table 13
Overview of all test instances from SET-I, SET-II, and SET-III and corresponding best formulations.
Set|V|d/|E||L|aBest  formulationSet-I1000.2501ECsn100ECsn, ECsnh125ECsn0.550ECsn, ECn, ECsnh100ECn, ECsnh125ECn, ECsnh0.850ECsn, ECn100ECn, ECsnh125ECsn, ECn, ECsnh2000.2100ECsn, ECsnh200ECsn250ECsn, ECsnh0.5100ECsn200ECsn250ECsn, ECsnh0.8100ECsn200ECsn, ECsnh250ECsn, ECsnhSet-II100040005EC* (several variants having same performance)10EC* (several variants having same performance)20EC* (several variants having same performance)Set-III1000.051/4·|E|Several methods having same performance3/4·|E|CEFtn0.21/4·|E|ECtñ3/4·|E|DCuttnc0.51/4·|E|ECtño3/4·|E|ECtnc0.051/4·|E|2EC* (several variants having same performance)3/4·|E|ECtñob, ECtnc0.21/4·|E|ECtñob, ECtnh3/4·|E|DCuttñobc0.51/4·|E|ECtnob3/4·|E|ECtnoc0.051/4·|E|5Several methods havingt≤03/4·|E|DCuttñc0.21/4·|E|ECtn3/4·|E|DCuttnco0.51/4·|E|ECtn, ECtnh3/4·|E|ECtnob, ECtnh10×10301EC* (several variants having same performance)50ECsnob80DCutsñob (best relaxation)20×2030ECsn, ECn50ECsn80DCuttñ (best relaxation)


### 4.4. Comparison to Other Work

In this section, we present direct comparisons to existing work, in particular [16]. Table 14 shows the results presented in [16], running times have been rounded to integers. Formulation “MLSTb” corresponds to formulation SCF of this work. Formulation “MLSTc” only uses a weaker coupling of labels to edges, given by the following inequalities:(4.1)∑(i,j)∈Axij≤min⁡{|V|-1,A(l)}zl,∀l∈L.
Table 14 furthermore reports results for the implementation of the exact backtracking method from [1], labelled with “MLST-CL”. Table 15 shows the running times of selected MIP variants in comparison to our reimplementation of the flow formulation “MLSTb” from [16] (SCF). Formulation ECtn is clearly superior to the others, all instances have been solved in less than one second. Higher running times of SCF as opposed to “MLSTb” can be explained due to the fact that the SCIP framework [26] has been used for the implementation of SCF whereas “MLSTb” has been implemented with the ILOG CONCERT framework [27].Table 14
Running times in seconds reported in [16], rounded to integers.
l510205102051020n2050100MLSTb000001013MLSTc000001017MLST-CL000000001l510205102051020n2005001000MLSTb031519136243621MLSTc163443837151321994MLST-CL006007100360l510205102051020n2050———MLSTb0001098———MLSTc000694———MLST-CL0004500———Table 15
Running times for instances that have been created according to specification from [16]. The first column lists the method for the corresponding row. In parenthesis the corresponding method from [16] is reported.
l510205102051020n2050100avg (|LT|)2.02.53.82.43.35.03.04.16.6SCF (MLSTb)0000000019SCFtn000000001DCuttn000000001ECtn000000000ECsn000000000A* (MLST-CL)000000001l510205102051020n2005001000avg (|LT|)3.05.07.93.55.99.94.16.611.3SCF (MLSTb)339712938431961303SCFtn016041911351DCuttn0041321121367ECtn000000000ECsn000000000A* (MLST-CL)00130015900609d0.20.50.80.20.50.8———n2050———avg (|LT|)7.13.52.23.03.97.6———SCF (MLSTb)000234025———SCFtn000301———DCuttn000522———ECn000000———ECsn000000———A* (MLST-CL)0006700———Table16 shows the results of selected MIP variants in comparison to the exact A* backtracking-search procedure used in [12]. The A*-algorithm is very effective for instances with small optimal objective value, but instances with larger objective values or large sets of labels cannot be solved. The time limit imposed by the authors of [12] was three hours. It is important to note that the running times listed in Table 16 are not directly comparable, as the authors of [12] list the computation time at which the best solution was obtained, and also different hardware has been used. For some groups, where A* could not solve all instance (indicated by “NF”), the MIP method was able to do so. Furthermore, it is reported if the MIP method could solve some but not all instances within some group. In any case the average objective value for the ten instances of each group is reported in column “avg(|LT|)”, also considering the best feasible solutions that have been found within the time limit of two hours. If all instances have not been solved to optimality, this is indicated with “(*)” in this particular columns.Table 16
Comparison to results reported in [12] for the A*-algorithm. Columns MLSTECn list the average total running times for each group of this particular MIP in seconds, columns A* list the running times in seconds (rounded to integers) reported in [12], at which the best solution was found.
|V||L|davg (|LT|)A*MLSTECtnopt|V||L|davg (|LT|)A*MLSTECtnopt100250.81.800104001000.82.0n/a6010100250.52.000104001000.52.2n/a6110100250.24.500104001000.25.8 (*)n/aNF8100500.82.000104002000.83.0n/a81710100500.53.000104002000.5NAn/aNANA100500.26.7100104002000.29.3 (*)n/aNF01001000.83.002104004000.8—n/aNF01001000.54.729104004000.56.2 (*)n/aNF01001000.29.7NF6104004000.214.6 (*)n/aNF01001250.84.0017104005000.8—n/aNF01001250.55.218011104005000.57.3 (*)n/aNF01001250.211.0NF12104005000.217.1 (*)n/aNF0200500.82.003105001250.82.0015710200500.52.202105001250.52.6019610200500.25.2510105001250.26.3 (*)NFNF22001000.82.6028105002500.83.052192102001000.53.4019105002500.54.3 (*)NFNF12001000.27.9NF191105002500.210.3 (*)NFNF02002000.84.023911105005000.84.8 (*)NFNF02002000.5—NFNF95005000.56.9 (*)NFNF02002000.2—NFNF75005000.216.4 (*)NFNF02002500.84.021301105006250.85.1 (*)NFNF02002500.5—NFNF95006250.58.4 (*)NFNF02002500.2—NFNF35006250.219.0 (*)NFNF0In general, it can be observed that relatively small instances could be solved efficiently by the MIP approach, but, for larger instances with|V|=400 and |V|=500, it generally fails to produce provable optimal solutions within the allowed time limit.


### 4.5. Summary

For all formulations, the node-label-constraints (3.22) significantly improved running times and reduced the number of branch-and-bound nodes. Despite its relatively poor LP-relaxation, formulation ECtn turned out to be superior to the other ones for a broad class of test instances, which is mainly to the fast cut separation and the low number of involved variables. Amongst the other considered formulations, DCuttn is superior to ECtn for dense graphs with a huge number of labels.The odd hole cuts (3.25) significantly improved running times and number of branch-and-bound nodes for some classes of instances, in particular when branching rules are deduced from the label sets corresponding to the found odd holes. Using BCP for dynamically adding new labels during the solution process turned out to be beneficial only in the case where the input instances significantly deviate from random label assignments, that is, where the optimal solution is much lower than the expectation value of randomly assigned labels. However, such solutions may likely easily be found also by heuristic methods. Nevertheless, this could remain the only way to prove optimality for “easy” large-scale instances.


## 4.1. Test Instances

The first set is the publicly available benchmark set used in [6, 10, 12, 13]. We refer to this data set as Set-I. It consists of graphs with 100 to 500 nodes and various densities d∈{0.2,0.5,0.8}, defined by |E|=d·(|V|·(|V|-1)/2), and different numbers of labels |L|=l/4,l∈{1,2,4,5}. The instances are organized in groups of ten for each configuration of d and |L| for each |V|. So far, primarily metaheuristics have been applied to this instance set, but also an exact algorithm based on A*-search, as reported in [12].The second test setSet-II is created following the specification of the instances used in [16], in order to obtain comparable results to the MIPs presented therein. This set is organized in four groups. In contrast to SET-I, the instances of the first two groups just contain very few labels, that is, |L|∈{5,10,20}. The number of nodes ranges from 20 to 1000, and network densities are set to |E|=4·|V|. Moreover, this set contains various grid-graphs (group 3) of sizes 2×10, 4×5, 2×18, 3×12, and 6×6. The fourth group contains instances with |V|∈{20,50} and |L|=|V| and various network densities d∈{0.2,0.5,0.8}.In addition to SET-I and SET-II we created a further test setSet-III containing also instances with multiple labels assigned to the edges. The construction is performed by first creating a spanning tree and assigning labels from set L*⊆L to its edges. Usually L*=L if not stated otherwise, but |L*|≪|L| is used to study the effect of having optimal solutions with significantly less labels than for completely random label assignment for the particular graph properties. Next further edges are added until a specified density d·(n·(n-1))/2,0<d≤1 or specified number of edges m∶=|E| is reached. Then, we randomly assign all labels not used yet. In the final step we iterate over all edges and assign further labels by uniform random decision. Parameter a specifies how many labels can be assigned to each edge, if not stated otherwise a=1. Instead of directly using |L| as a parameter, we may also specify the size of the label set by parameter r=|L|/|E|,0<r≤1. In contrast to the other instances, the instances of SET-III have relatively high values of r, that is, r=1/4 and r=3/4. Although such instances are less likely to occur within practical applications regarding telecommunication network design, they may be relevant for other scenarios, as for instance the compression model based on the MLST problem presented in [17].


## 4.2. Test Environment

The generic framework presented in Section3 has been implemented in C++ (gpp-4.3) within the SCIP framework [26]. The standard plugins have been used for all computational tests unless explicitly stated otherwise. In addition some branch-and-cut algorithms (not involving any pricing procedures) have been implemented within the ILOG CONCERT framework [27] for comparison purposes. As LP solver ILOG CPLEX (in version 12.0) [27] has been used for both frameworks.All computational tests have been performed on an Intel Xeon E5540 processor operating at 2.53 GHz and having 24 GB for total 8 cores. The operation system is Ubuntu 9.10 with Linux-kernel 2.6.31. All runs have been performed in single-threaded mode, CPU times have been limited to 7200 seconds, unless stated otherwise.


## 4.3. Comparison of Described Methods

In this section, we present a comparison of the described formulations based on computational tests. Furthermore, we analyze the impact of particular “components” to each of the formulations. These components consist of the node-label-inequalities (3.22), the extended node-label-inequalities (3.23), the strong linkage of the edges to the edges (3.21), which can, however, only be used if only one label is assigned to the edges and the number of edges is not fixed by (3.5). Table 1 provides an overview of these components and corresponding notation. After the comprehensive analysis and comparison of the particular methods in this section, we compare the results of the newly proposed methods to previous work in Section 4.4.


### 4.3.1. MIP Formulations

In this section, we primarily focus on the comparison of formulations EC, DCut and SCF. However, particularities like node-label-constraints (3.22), or fixed number of edges (3.5), or the direct linkage of labels to edges (3.21), may significantly change the picture regarding the superiority of one method over another one. For this reason, we present the results not only for three formulations, but rather four to five variants of each formulation. Recall, that directly linking the labels to edges by (3.21) is only possible for instances with one label assigned to each edge (3.21), that is, a=1 and is generally not possible for flow-formulations. In order not to be biased towards some particular class of instances, we report these results for each of the three instance sets.Tables2 and 3 show the results for instances of SET-I with |V|=100 and |V|=200. These instances include graphs with various densities d∈{0.2,0.5,0.8}, where |E|=d·(|V|·(|V|-1)/2), and different numbers of labels, that is, |L|=1/2·|V|,|L|=|V|, and |L|=5/4·|V|. In these tables, as well as in the following ones, we report the following entities for each method and group of instances.  Columns “cnt” contain the number of instances within each group, which is 10 in most of the cases. The reason for less than ten instances reported is not being able to finish some instances with particular formulations due to high memory requirements. Columns “opt” report the number of instances that have been solved and proved to be optimal within the time limit. In columns “obj” the average objective value for all instances in the group is reported. If all instances have not been solved to optimality, this value corresponds to the average value of feasible solutions that have been found within the timelimit. Average running times in seconds are then reported in columns “t”. The average number of branch-and-bound nodes is listed in columns “bbn”, the average number of generated cuts in column “cuts”. Results of the fastest method(s) for each group are emphasized with bold letters.Table 2
Comparison of selected variants of formulations EC, DCut, and SCF on the instances from SET-I with|V|=100.
|L|=50|L|=100|L|=125dalgcntoptobjtbbncutscntoptobjtbbncutscntoptobjtbbncuts0.2EC10106.772346510109.762387610729911.212393652843ECt10106.7834719610109.72524824149911.2343769871ECtn10106.7410017310109.7118573399911.2161401402ECn10106.7024310109.7912981799911.2332648594ECsn10106.7031310109.761127349911.212257089DCut10106.780116769110109.710131437877989811.214701964611403DCutt10106.7125145895410109.7478667639199911.2740102736450DCuttn10106.72112711610109.78610217299911.211514261017DCutn10106.711909610109.75711575999911.217631861868DCutsn10106.712948910109.75111905169911.212930861536SCF1026.87028136930−110010.3720019854−19012.4720017296−1SCFt1016.77133143226−110010.37200101319−19011.77200119683−1SCFtn10106.71583−110109.767673−19911.2851033−1SCFn10106.71583−110109.763673−19911.2841033−10.5EC10103.01746510104.7374558428210105.24465307630ECt10103.0146914810104.7175503933010105.21293249382ECtn10103.09713610104.73452416510105.239452277ECn10103.002010104.78221410105.291274ECsn10103.002010104.79173410105.21137012DCut10103.02174882721084.8385815810721410105.2315093164187DCutt10103.01904652561094.7347111770624610105.2179453663175DCuttn10103.056132810104.7401113345010105.2305633342DCutn10103.027122810104.7261159751810105.22501179401DCutsn10103.027235510104.7216153939010105.22251234362SCF10103.08501475−11005.0720011453−11005.872007586−1SCFt10103.07221597−11064.7531923618−11005.5720018169−1SCFtn10103.0221−110104.7211617−110105.2171298−1SCFn10103.0201−110104.7203617−110105.2176298−10.8EC10102.01221210103.01618489810104.0999431020ECt10102.011719610103.03614217910104.01352344130ECtn10102.014410210103.0241118710104.04439483ECn10102.001010103.013210104.0171020ECsn10102.001010103.024110104.017510DCut10102.025597651093.12367244012861004.0720069583525DCutt10102.01981271311093.11997270216351094.0508363633410DCuttn10102.08771910103.031437021610104.09231193408DCutn10102.04052210103.041893245710104.07801853546DCutsn10102.03332910103.01281619310104.07402154668SCF10102.0274103−11003.672002826−11004.072002752−1SCFt10102.0335−11004.072003035−11004.072002849−1SCFtn10102.0281−110103.0292−110104.0243349−1SCFn10102.0281−110103.0292−110104.0230349−1Table 3
Comparison of selected variants of formulations EC, DCut, and SCF on the instances from SET-I with|V|=200.
|L|=100|L|=200|L|=250dalgcntoptobjtbbncutscntoptobjtbbncutscntoptobjtbbncuts0.2EC1088.03770526821662110012.97200422892230310015.472003200918669ECt1078.0454143756766510013.6720043298800710016.07200437927293ECtn10107.912961425453910213.3687860643143610114.96761462961658ECn10107.92018379510512.2514618903397310313.863871445975207ECsn10107.91918322410712.143311822378110313.96153250129158DCut1008.8720010929897110014.572003850363210018.9720036813548DCutt1009.072004392403610014.572002896286610016.1720026532622DCuttn1078.1548713056803610013.072005588476310015.7720039823552DCutn1098.0339814653863710012.97200158771220010014.97200112079494DCutsn1098.0299614937765810012.77200192801356910014.772001371210837SCF1009.372001017−110014.57200634−110016.87200559−1SCFt1008.972003204−110013.572004733−110015.872005326−1SCFtn1088.033539362−110012.472006854−110014.172004343−1SCFn1088.034988308−110012.472006468−110014.172004099−10.5EC10103.47692082691005.8720086035391006.572005380456ECt10103.4145227445581005.87200103076471006.4720090841024ECtn10103.45704696781075.5424965509081006.5720015870861ECn10103.42512611095.4129114284121086.443235771531ECsn10103.4199211095.411761465361096.440496237118DCut904.1720010867281007.272003232651007.97200272215DCutt904.372006134691007.972002982901008.27200335307DCuttn1083.551359544811006.672005573491007.47200420282DCutn1083.5313210795071006.2720017959291007.172001097564DCutsn1093.420549794121006.0720020729121006.772001432671SCF1004.37200124−11007.0720069−11007.8720054−1SCFt1003.97200207−11006.57200166−11007.37200150−1SCFtn10103.41102270−11005.77200828−11006.57200839−1SCFn10103.41204270−11005.77200749−11006.47200728−10.8EC10102.628032968161004.072001132161005.07200164048ECt10102.6304036505051004.0720021466561024.470646763757ECtn1092.7273910361310104.0503868196341094.129021331776ECn10102.67627310104.011225975110104.060933243ECsn10102.6281110104.09114845110104.03017771DCut403.072001521341008.272011051101007.172006970DCutt1003.972001511711005.272021101121006.87200111112DCuttn1033.36344142671004.672001771021005.5720012098DCutn1032.7652811034441004.272003291701004.97200158126DCutsn1062.651357992921004.072005562271005.07200226140SCF1002.9720069−11004.9720035−11005.5720033−1SCFt1022.8592354−11004.3720058−11005.1720135−1SCFtn1092.6417774−11014.06929391−11034.76712264−1SCFn1092.6418379−11014.06973375−11024.76871229−1From Tables2 and 3 we can already observe that the difficulty of solving these instances is strongly correlated to the objective function values of the instances. Higher values, in particular those larger than ten, require significantly more B&B-nodes, and the separation of more cuts. This also implies longer average running times. This property holds for all of the considered formulations. The results in Tables 2 and 3 show that formulation ECsn consistently gives the best results for these instances. The single-commodity flow formulations show a slightly better performance than the directed-cut formulations for most of the instances.The strength of the node-label-inequalities (3.22) is also demonstrated by the results in Tables 2 and 3. Their addition to the plain formulations does not only yield a significant speedup, but also enables to solve more instances regarding the set with |V|=200. The difference between Inequalities (3.22) and their extended form, given by Inequalities (3.23) is examined in Section 4.3.2. Regarding Equation (3.5) no clear conclusion can be drawn from these instances. If, however, combinations of these components are considered, the variants only using the node-label-constraints are superior in most of the cases. For formulations EC and DCut it is also possible to directly link the edges to the labels by   (3.21). In most of the cases, this yields the best results, when combined with the node-label-inequalities for both formulations, and in particular in combination with EC the overall best results.Table4 reports the results for the same formulations for the instances of SET-II. These instances have the major difference to contain only graphs of extremely low density d and just very few labels. Again, we can observe a clear superiority of formulations ECsn and ECn, which are able to solve all these instances with average running times of less than  half second.Table 4
Comparison of selected variants of formulations EC, DCut and SCF on the instances from SET-II.
|L|=5|L|=10|L|=20|V|, |E|algcntoptobjtbbncutscntoptobjtbbncutscntoptobjtbbncuts200,  800EC10103.001010105.003010107.90132ECt10103.00223610105.00831510107.9247582ECtn10103.00215710105.00624910107.9120515ECn10103.001010105.001010107.9062ECsn10103.001010105.001010107.9061DCut10103.0163810105.04146310107.914127171DCutt10103.0362610105.07183710107.918161173DCuttn10103.0042910105.0273610107.982163DCutn10103.0022410105.0064910105.00649DCutsn10103.001010105.001010107.9061SCF10103.022−110105.0932−110107.969800−1SCFt10103.032−110105.0932−110107.971800−1SCFtn10103.001−110105.013−110107.9616−1SCFn10103.001−110105.013−110107.9616−1500,  2000EC10103.501010105.902010109.90120ECt10103.53262110105.96783310109.916441129ECtn10103.52154110105.95676310109.916251385ECn10103.501010105.901010109.9080ECsn10103.501010103.501010109.9070DCut10103.5553410105.914147610109.948152184DCutt10103.51372510105.928153410109.968181144DCuttn10103.5231610105.9983310105.99833DCutn10103.5124610105.9366710109.92020139DCutsn10103.5128210105.9366010109.92019129SCF10103.5103−110105.92818−110109.9372661−1SCFt10103.5113−110105.92918−110109.9384661−1SCFtn10103.501−110105.943−110109.92020−1SCFn10103.501−110105.933−110109.91820−11000,   4000EC10104.101010106.6010101011.30130ECt10104.1201118210106.64661762101011.3121543514ECtn10104.13001382310106.623462660101011.3108262909ECn10104.101010106.6010101011.3070ECsn10104.101010106.6010101011.3060DCut10104.11654010106.64713259101011.3144191275DCutt10104.15462210106.6902036101011.3240189150DCuttn10104.1732310106.626726101011.31033647DCutn10104.112118410106.6135195101011.36426355DCutsn10104.111117810106.6476495101011.35724253SCF10104.1302−110106.69914−1101011.31243416−1SCFt10104.1312−110106.69614−1101011.31303416−1SCFtn10104.111−110106.6123−1101011.35231−1SCFn10104.111−110106.6123−1101011.34831−1In Tables5, 6, and 7, results for the instances from SET-III are reported. Table 5 shows the results for instances with |V|=100 and a=1, that is, one single label assigned to the edges. As already mentioned in Section 4.1, this instances differ from the previous ones in the way that they contain a higher number of labels, that is, r=1/4 and r=3/4 with r=|L|/|E|. It can be observed that it is beneficial to limit the number of edges to |V|-1 by (3.5) in this case. Thus, the stronger LP-relaxation implied by this restriction is beneficial in the case of higher values of r. For instances with r=1/4 formulation EC still shows the best performance, but DCut provides better results in the case of r=3/4. Hence, the strong LP-relaxation becomes even more important if |L| is in the same order of magnitude as |E|.Table 5
Comparison of selected variants of formulations EC, DCut and SCF on the instances from SET-III with|V|=100; α=1.
|L|=1/4·|E||L|=3/4·|E|dalgcntoptobjtbbncutscntoptobjtbbncuts0.05EC101019.621892172210061.67200108393124719ECt101019.6236887602610151.36480178187195559ECtn101019.6144944448610251.25760163875182801ECn101019.621491124610062.57200103413119245ECsn101019.61131396610055.57200133833151889DCut101019.6355214302610050.77200367146337417DCutt101019.6344174248710449.843817662955867DCuttn101019.612114875910649.831958715260318DCutn101019.613143794110050.47200337882315950DCutsn101019.61131396610050.47200360801343056SCF10319.65576987720−110051.572001815207−1SCFt10919.61354513872−110550.038233081605−1SCFtn101019.6315160−110849.91508800971−1SCFn101019.6499415−110050.67200894051−10.2EC10115.1709920808211736210045.172006230063102ECt101014.8675547422379010436.56326138547137549ECtn101014.8344363861674510237.16450120465121687ECn10215.363691366579492710046.072004016341557ECsn10414.848942311489506210039.272006516763256DCut10016.37200480733531610038.9720011978987861DCutt10614.83196551693714410635.837066176247626DCuttn101014.883513677869810735.824323609927852DCutn10015.77200391322970010038.572004857640239DCutsn10115.67134783395754610038.072008864573235SCF10017.0720014435−110040.5720039472−1SCFt10015.57200173479−110037.87200480980−1SCFtn10914.8240131073−110136.16495152260−1SCFn10015.2720063078−110038.4720029479−10.5EC10015.87200695543626010038.872005415355751ECt10813.32570624873042510530.740645144250552ECtn9813.21400341061876910431.050385960557375ECn10016.27200359441832310038.972002898431127ECsn10013.772002967828896210033.872006343064801DCut10015.472007645429110036.072003100819324DCutt10613.551529463903610630.343311600313285DCuttn10513.545579195854310730.23552123379780DCutn10015.472005807378510036.6720069355131DCutsn10014.4720012834815410032.47200141089913SCF10016.472001345−110034.572003160−1SCFt10014.6720019313−110032.3720035869−1SCFtn10513.547569842−110230.7584216960−1SCFn10014.572006765−110033.172002327−1Table 6
Comparison of selected variants of formulations EC, DCut and SCF on the instances from SET-III with|V|=100, a∈{2,5}.
|L|=1/4·|E|,a=2|L|=3/4·|E|,a=2|L|=1/4·|E|,a=5|L|=3/4·|E|,a=5dalgcntoptobjtbbncutscntoptobjtbbncutscntoptobjtbbncutscntoptobjtbbncuts0.05EC101016.673222327710042.87200112158123363101010.5015245210021.47200111275106501ECt101016.66311657990110735.02558113102106934101010.5036240010420.84763178547160611ECtn101016.6124707408010735.0237510217993532101010.5030635910620.63467143690125295ECn101016.621883195610042.47200116472124838101010.5015842610021.57200107718103093DCut101016.6314173240910035.17200374197286064101010.5724723810020.57200375009236293DCutt101016.63635232114101034.711267254842101010.51035030110920.510667558746230DCuttn101016.6161162787101034.76146613696101010.55115134101020.56984587025073DCutn101016.611102669410035.07200376389268567101010.539511510720.54126215290129837SCF10116.77153896512−110037.17200701281−110910.52318507224−110021.87200276624−1SCFt10716.640381339695−110135.070463581766−1101010.51580440888−110021.072001707957−1SCFtn101016.6293894−1101034.7609239014−1101010.54284−110920.52218462195−1SCFn101016.66711755−110035.87200666248−1101010.55329−110020.97200720521−10.2EC10312.3652126824011707910031.87200727206934510107.833642365853498710019.57200159231107082ECt10812.11840815984010910326.2584514156812722910107.82653987577310315.1518417149089976ECtn101011.9629420522063710326.3524211955010735810107.81281244165110315.1514013998390176ECn10712.142851660547945710034.07200498595094010107.8104156147816610019.0720011518889434DCut10013.47200434123249710027.3720072779487721017.96892706903650710016.672003335023851DCutt101011.91477178411318310725.6295755433381211057.85653677544256010414.954235580043216DCuttn101011.96815906518010925.61489249311766310107.8162815222955210614.844064462832312DCutn10013.27200395993022510027.4720031085234201077.84679654152581210015.872001576111375SCF10014.3720013282−110030.0720019389−11008.8720022933−110018.1720012399−1SCFt10012.97200105555−110027.07200320786−11008.17200107916−110015.87200109149−1SCFtn10812.1190918528−110425.9533887496−110107.8166911756−110215.1632744397−1SCFn10012.8720047542−110027.6720015439−11097.8415159801−110016.0720010494−10.5EC10011.57200982573800010028.4720093989774941016.96785101172724210014.572005051829040ECt101010.963242951526810123.46487854857100310106.9612279367859513.1380410066638284ECtn101010.950622467643210326.3524211955010735810106.925566045329613.034727258238165ECn10011.37200378581836510029.0720044406399261007.0720029141214310016.27200117516165DCut10011.872009769550310030.472001585295161007.1720011487599510015.2720057423186DCutt10011.37200130891156010822.54745958588511007.472007977621310013.8720078277958DCuttn10511.2566411813978610522.84259885084811067.150895318352910413.1574379347389DCutn10011.972007129442610027.17200473829961017.167177337317210015.2720026821652SCF10013.272001477−110026.872001628−11008.072002606−110016.27200923−1SCFt10012.1720013970−110024.3720026439−11007.672006757−110014.3720010634−1SCFtn10610.948416975−110023.4720012529−11077.042383003−110213.359236203−1SCFn10011.872009232−110025.072003000−11007.0720021470−110014.472004668−1Table 7
Comparison of selected variants of formulations EC, DCut and SCF on the grid graph instances from SET-III with|E|≈4·|V|.
|V|=10×10|V|=20×20|L|algcntoptobjtbbncutscntoptobjtbbncuts30EC10109.2420411540101011.5617496400ECt10109.2626411843101011.518375475819ECtn10109.2416391544101011.59137574231ECn10109.211369656101011.5173602200ECsn10109.211281601101011.5173558175DCut10109.261494832402211.05224623337505DCutt10109.29361964135101011.530292295619238DCuttn10109.23418921710101011.5627405810961DCutn10109.218151213641012.072003924766DCutsn10109.219135623141013.072002623113SCF10109.2815118270−110011.8720022192−1SCFt10109.264190448−110011.7720022091−1SCFtn10109.2171280−1101011.52513127−1SCFn10109.2121008−1101011.52183076−150EC9813.01018546534103610917.1434146460231132ECt9713.11959993977368710017.07200301858167539ECtn9813.015788399667834101017.03834212265107170ECn9912.91292529916378101017.0134720822111217ECsn9912.9662233913131101017.010871932138470DCut9912.986767360378737017.372002939047832DCutt9912.91032747184208810017.272003224833668DCuttn9912.9302205961290710017.072008617264236DCutn9912.933628974176137016.37200334536785DCutsn9912.920720951133237015.7720064823682SCF9013.37200368322−110018.5720013103−1SCFt9013.27200741954−110018.5720019592−1SCFtn9912.921521632−110017.17200131296−1SCFn9912.929934004−110817.15532169723−180EC10019.5720013460811837710025.07200199143139246ECt10019.9720023178920866110024.97200143214104486ECtn10019.6720022961920278710024.87200146616112030ECn10019.5720016219213890410024.67200305748138953ECsn10018.9720022816717674110024.67200299188134344DCut10018.8720025282622527310025.572003175632402DCutt10018.972002481232165139019.872002412125391DCuttn9018.7720028362522094010025.272004360444755DCutn10018.872002394891970738024.672005422662124DCutsn10018.972002489662131577025.172002526246754SCF10019.77200285092−110027.072009767−1SCFt10019.27200948572−110028.0720022180−1SCFtn10019.07200689593−110025.3720068435−1SCFn10018.87200863039−110025.2720099643−1With a single exception, the same effect can be observed for the instances witha∈{2,5} reported in Table 6. The effect of more than one label being assigned to the edges seems to make the problem easier to solve, but the effect is relatively small. It is important to note, that directly linking the labels to the edges, which was beneficial for the instances with a=1, cannot be applied to instances with larger a.Table7 shows the result for grid-graphs with 100 and 400 nodes and |L|∈{30,50,80}. The average optimal objective value on these graphs is relatively high, which makes them difficult to solve. However, all instances with |L|∈{30,50} could be solved to optimality by formulation ECsn, which showed the overall best performance on this class of instances.Having now analyzed the main variations of the discussed formulations we draw our attention to further approaches and enhancements that have been proposed in Section3.


### 4.3.2. Further Methods

In Section4.3.1 the node-label-inequalities (3.22) have been shown to be of utter importance for a strong formulation. In Section 3.3 we have also presented an extension of this idea, where two nodes are considered instead of just one. This led to the class of Inequalities (3.23). Table 8 shows a comparison of formulations ECt and DCutt with on the one hand the node-label-inequalities (3.22) and on the other hand additional Inequalities (3.23). In particular for formulation ECt these further inequalities turn out to be useful in many cases. They do not only speedup the solution process, but moreover frequently enable to solve more instances to provable optimality. However, also the opposite is often the case. It is therefore not possible to decide which approach is superior over the other based on the available data. On grid-graphs Inequalities (3.23) have not been beneficial at all.Table 8
Comparison of formulationsECt and DCutt with Inequalities (3.22), indicated with index n, and with additional Inequalities (3.23), indicated with index ñ.
ECtn/DCuttnECtñ/DCuttñ|V|,|E|,a,|L|cntoptobjtbbncutscntoptobjtbbncuts100,247,1,61101019.61449444486101019.60499492101019.6121148759101019.61915771034100,247,1,18510251.2576016387518280110750.02174657816872310649.83195871526031810549.842848676962183100,900,1,247101014.83443638616745101014.8177183526741101014.8835136778698101014.819492697316494100,900,1,74210237.1645012046512168710735.82403480384539810735.82432360992785210835.718222052215153100,2475,1,61810813.2140034106187699813.21801464692236310513.545579195854310413.65417107739933100,2475,1,185610431.05038596055737510730.32506272412495710730.2355212337978010830.2290737153689100,247,2,61101016.61247074080101016.61601498101016.6161162787101016.6211348907100,247,2,18510735.0237510217993532101034.7932693274101034.76146613696101034.71914251226100,900,2,247101011.96294205220637101011.99125510620864101011.968159065180101011.915231643512011100,900,2,74210326.3524211955010735810725.83265696855378510925.61489249311766310925.615831707612240100,2475,2,618101010.9506224676432101010.955837153392110511.2566411813978610111.770501250311444100,2475,2,185610423.25213619085329410323.25757731455765710522.842598850848110822.5364941854254100,247,5,61101010.50306359101010.50248306101010.55115134101010.511316321100,247,5,18510620.6346714369012529510920.512026057149983101020.56984587025073101020.54983677420977100,900,5,24710107.81281244165110107.82883932482510107.816281522295521057.856756649942125100,900,5,74210315.15140139983901769415.043441555897319810614.84406446283231210414.951715043438692100,2475,5,61810106.9255660453210106.9624279367851067.15089531835291007.4720083036431100,2475,5,185610613.03472725823816510613.038481036354165110413.157437934738910113.671918419861710×10,360,1,3010109.241639154410109.262641184310109.2341892171010109.2906196413510×10,360,1,509813.0157883996678349813.01877102421756929912.930220596129079912.91034747184208810×10,360,1,8010019.6720022961920278710019.9720025195722694110018.772002836252209409018.8720028328824139920×20,1520,1,30101011.59137574231101011.517675475819101011.5627405810961101011.52866229561923820×20,1520,1,50101017.0383421226510717010117.0719432605117805810017.07200861726423610017.27200347423577920×20,1520,1,8010024.8720014661611203010024.9720015052911012010025.27200436044475510020.672002571826997Further formulations, considered in Section3, are based on the property that a tree must not contain a cycle by definition. Formulation MTZtn requires just a polynomial number of variables, but contains constraints with infamous “Big-M” constants, as the SCF formulation does. On the contrary CEF contains an exponential number of Inequalities (3.15), which need to be separated as cutting-planes as for the DCut or EC formulation. Due to their fast separation by a simple shortest-path computation, other formulations may benefit from additionally using cycle-elimination cuts. Corresponding results are reported in Table 9, column “cec” lists the average number of separated cycle-elimination cuts. Whereas MTZtn and CEFtn show a relatively weak performance on the instances with r=1/4, they provide good results in the case of r=3/4. In particular, for the low-density graphs CEFtn could solve all instances to optimality, which no other method was able to do. For the dense graphs best results are obtained by DCuttnc and ECtnc.Table 9
Comparison of various formulations based on cycle elimination, that is, the Miller-Tucker-Zemlin formulation MTZ and the CEF on the instances from SET-III with|V|=100, a=1. Furthermore results for connectivity-based formulations (EC and DCut), enhanced by cycle elimination inequalities are reported.
|L|=1/4·|E||L|=3/4·|E|dalgcntoptobjtbbncutsceccntoptobjtbbncutscec0.05MTZtn10519.73931502063−1−110749.93112721279−1−1CEFtn10619.63000135407−116638101049.890194205−16389CEFtñ10519.63998155632−11764210749.92208208113−114321ECnc101019.61413531215910050.372005328361707981783ECtnc101019.6129151539610749.8256662656446075502DCutnc101019.61314339315510050.472003766493512881630DCuttnc101019.61310297009410749.82291367452774828590.2MTZtn10715.0427645276−1−110535.8427287003−1−1CEFtn10714.9321736913−1329810735.7231391215−15422CEFtñ10315.2530761399−1569010735.7266840566−12478ECnc10015.672003183514311810037.8720059337153330ECtnc101014.87011068719667010835.7187151079155443426DCutnc10015.97200392252975517110039.4720047294392063DCuttnc101014.873711214721258110835.71537217211379514000.5MTZtn10513.555557818−1−110330.9565813851−1−1CEFtn10513.650388686−176310730.1444419156−11653CEFtñ10313.657918399−1106310530.555706646−1711ECnc10014.172003463263510032.77200649711825ECtnc10713.53865877211691310930.1211291201344665DCutnc10015.67200535333952410038.27200696453576DCuttnc10813.533947452643367510930.0242774755918576Table10 shows the results that have been obtained by including primal heuristics into the branch-and-bound algorithm. Formulations ECtn, ECsn, DCuttn, and DCutsn are considered for this purpose. As indicated by preliminary experiments it turned out to be advantageous only to use the primal heuristics in the root node, as they were generally not able to find improved solutions based on the information provided by the LP-solution in other B&B-nodes. Embedding MVCA in B&B has a positive effect w.r.t. the variants “tn” of formulations EC and DCut, but a negative impact concerning variants “ts”.Table 10
Comparison of best formulations used without and with primal heuristics, that is, MVCA and ACO.
|L|=1/4·|E||L|=3/4·|E|dalgcntoptobjtbbncutscntoptobjtbbncutsECtn101019.6144944448610251.257601638751828010.05ECsn101019.61131396610055.57200133833151889DCuttn101019.612114875910649.831958715260318DCutsn101019.610133689510649.831958715260318ECtn+MVCA101019.6125474486610251.35771145352166307ECsn+MVCA101019.621635125510052.37200137776154933DCuttn+MVCA101019.611105671410649.829025728241009DCutsn+MVCA101019.612153099310050.47200371927343330ECtn+ACO101019.612442539168449.63600107155110775ECsn+ACO101019.62133997810049.97200134930151941DCuttn+ACO101019.6109376279449.840197450652846DCutsn+ACO101019.611130382810050.47200371927343330ECtn101014.8344363861674510237.164501204651216870.2ECsn10414.848942311489506210039.272006516763256DCuttn101014.883513677869810735.824323609927852DCutsn101014.883513677869810038.072008864573235ECtn+MVCA101014.8767524962853110236.96004120042120862ECsn+MVCA10414.849042122228987310038.772006330860554DCuttn+MVCA101014.879912503828410835.721693421925835DCutsn+MVCA10115.57067726585489410038.172008257567712ECtn+ACO101014.834531157143139536.041356736266292ECsn+ACO10314.953232282739441010036.172006434060405DCuttn+ACO101014.86401103471499635.825243556026632DCutsn+ACO10215.06977807255492510036.272008355369016ECtn9813.21400341061876910431.0503859605573750.5ECsn10013.772002967828896210033.872006343064801DCuttn10513.545579195854310730.23552123379780DCutsn10014.4720012834815410730.23552123379780ECtn+MVCA10813.31991404402399510530.542745320250948ECsn+MVCA10013.772002798957963310032.472006702666888DCuttn+MVCA10713.333216462585210930.0272884797236DCutsn+MVCA10014.3720011154722410032.272001487810082ECtn+ACO9713.3226144962257186231.354196148159297ECsn+ACO10013.772003453588005410031.172006446963099DCuttn+ACO10713.43534765969338530.53374105778304DCutsn+ACO10013.8720012035731910031.27200139199175


### 4.3.3. Odd hole Inequalities

We now draw our attention to the odd hole inequalities. Within preliminary tests, we determined a tight timelimit of 10−3 seconds for solving the MIP (3.26)–(3.38) to show a generally good performance. Two algorithmic variants are considered for the results reported in Table 11. The first version (denoted with index o) simply adds the found valid cutting-planes to the MIP. Alternatively, the set of labels corresponding to the obtained odd hole can also be used to deduce a branching rule. This was motivated by the observation that many lifted odd hole cutting planes, found by MIP (3.26)–(3.38), were not strong enough to define facets w.r.t. the involved label variables. As a consequence, these variables remained fractional after the cutting-plane was added to the MIP. However, odd holes provide important information and references to situations where special configurations of label-variables artificially reduce the LP-relaxation. Hence it is likely that immediately branching over these variables may be beneficial. This is done by inserting all labels of the odd hole into a global queue, and always branch over such a variable unless the queue is empty. Index ob denotes this approach in Table 11. Odd hole cuts are separated with lowest priority amongst the user-defined cutting-planes, and are only separated in levels of the B&B-tree which are multiples of ten.Table 11
Comparison of formulationsECt and DCutt with and without using odd hole ienqualities. Index o denotes if odd hole inequalities are separated, index b indicates that odd hole inequalities have been used to induce branching over related label variables.
ECtn/DCuttnECtno/DCuttnoECtnob/DCuttnob|V|,|E|,a,|L|cntoptobjtbbncutsoptobjtbbncutsohoptobjtbbncutsoh100,247,1,61101019.614494444861019.62556925141231019.6175226470119101019.61211487591019.613116377211019.61311217331100,247,1,18510251.25760163875182801251.25760144151159964194251.1576014356215932117310649.831958715260318649.83214833475832211649.83197859976058513100,900,1,247101014.834436386167451014.841737993182841341014.83433463915817120101014.88351367786981014.889214659936411014.898715816101312100,900,1,74210237.16450120465121687336.863771268191289241251236.76007119218119667130810735.824323609927852735.82369347172634877735.82371337572608361100,2475,1,61810813.214003410618769813.324994859928883174813.31820354792177513810513.5455791958543713.54261830576159713.34318832277698100,2475,1,185610431.050385960557375530.841335307952191709431.04499549455425461410730.23552123379780930.028278780680951930.027788061689839100,247,2,61101016.612470740801016.61451484496231016.6134987436320101016.61611627871016.617116178801016.61611467751100,247,2,18510735.0237510217993532635.13485137028125999272735.0243110259590520178101034.761466136961034.7695073408181034.722175816304100,900,2,247101011.96294205220637912.099748954228661371011.98574193321903129101011.9681590651801011.98918242686861011.910008936773411100,900,2,74210326.35242119550107358326.253951184831043411312426.3484110707294593122010925.614892493117663925.61603241121803182925.61443238371680167100,2475,2,618101010.95062246764321010.9748289179107441010.93881777036841410511.25664118139786511.257361095894677611.157271115593168100,2475,2,185610423.252136190853294123.864907452564822822223.56298722566205975410522.8425988508481722.636427480707322822.534797831717320100,247,5,61101010.503063591010.5030635911010.512673381101010.551151341010.5511513401010.551151340100,247,5,18510620.63467143690125295420.74461157779137051937620.63047116829103068673101020.56984587025073920.5787438832492112920.5783451442557510100,900,5,24710107.812812441651107.8134125216312107.815713710862310107.81628152229552107.815131507192221107.815401515393650100,900,5,74210315.1514013998390176415.0483813275683094702415.044581256657832765110614.844064462832312514.94520458183317222514.94392444353226718100,2475,5,61810106.92556604532106.925365815190106.9262670157701067.150895318352967.0509255033685067.05093544736080100,2475,5,185610613.034727258238165712.931326247333275255712.92343501062408715810413.1574379347389313.36505889684209313.1621382597770810×10,360,1,3010109.2416391544109.251427135010109.25142713841110109.23418921710109.232168515105109.23417111576610×10,360,1,509813.015788399667834813.015508111266089310912.961954900424881459912.93022059612907912.9387251421618023912.92981993812261810×10,360,1,8010019.67200229619202787019.872002119031868851086019.57200211561188812110210018.77200283625220940018.87200232626190432403019.0720022397018883238120×20,1520,1,30101011.591375742311011.51073749431001011.5106379942490101011.56274058109611011.575340281156701011.5705411211261020×20,1520,1,50101017.03834212265107170917.0423220992310575532917.043242100031073853910017.072008617264236017.0720077221606036017.072008045359244420×20,1520,1,8010024.87200146616112030024.87200133250102086626024.9720013164110147957710025.272004360444755025.27200392624170421025.27200394514295219The results in Table11 show that the odd hole inequalities are beneficial in many cases, in particular when used to deduce branching rules from the corresponding label-variables. For instances from SET-I and SET-II, almost no odd holes have been found with the described parameter settings. For dense graphs it is less likely to find odd holes that are violated by the current LP-solution, as each node is incident to many edges. Hence |L(v)| is in the same order of magnitude as |V| in the expected case. This implies many nonzero lifting coefficients in Inequalities (3.25), reducing the chance of finding a valid inequality that is actually violated by the current LP-solution. Hence, the separation of odd hole inequalities is most beneficial for sparse graphs. Also the number of labels compared to the number of edges has an impact on the efficiency of the odd hole separation. If the number of labels is relatively low, the expected label frequency νl will be high. This implies high values for the lifting coefficients γl, which in turn reduces the chance of finding violated odd hole inequalities. If, on the other hand, the number of edges is too high, odd holes are generally less likely to occur, as the sets L(v)∩L(u), for all v,u∈V can be expected to be very small or even empty.


### 4.3.4. Branch-and-Cut-and-Price

Additionally, using the column generation approach within the B&C framework, that is, branch-and-cut-and-price (BCP) is only beneficial for a very special class of instances. For most of the instances almost all variables are priced in during the solution process. The computational overhead for solving the pricing problem and resolving the MIP implies significantly higher running times in this case. However, if the instances consist of a high number of labels, and have an optimal solution that is significantly lower than the average optimal solution value when assigning the labels to the edges randomly in the instance construction process, BCP shows a superior performance. To study this effect, special instances have been created containing single optima having a relatively low number of labels. The computational results for these instances are reported in Table12. In particular for the larger instances a clear superiority of the BCP approach w.r.t. the corresponding B&C algorithm can be observed. For this special class of instances, the percentage of created label variables is always less than 30% of the total number of labels (reported in column “priced”). Although the importance of such instances may be quite limited for many purposes, the instances used for the data compression approach presented in [17] exhibit comparable properties. For the data-compression application presented therein, the BCP approach is thus a valuable and important mean for exactly solving large instances.Table 12
Branch-and-cut-and-price results for a special class of instances containing many labels and isolated optima with a relatively low number of labels.
|V|,|E|,a,|L|Methodcntoptobjtbbncutspriced100, 247, 2, 61ECtn10105.00132−1DCuttn10105.0017−1ECtnp10105.0016414DCuttnp10105.0011317100, 247, 2, 185ECtn101010.0011−1DCuttn101010.0012−1ECtnp101010.001211DCuttnp101010.00137100, 900, 2, 247ECtn10105.00130−1DCuttn10105.01115−1ECtnp10105.0017229DCuttnp10105.0021928100, 900, 2, 742ECtn101010.001442−1DCuttn101010.081325−1ECtnp101010.0249732830DCuttnp101010.012324125100, 2475, 2, 618ECtn10105.01246−1DCuttn10105.019415−1ECtnp10105.0165127DCuttnp10105.01141926100, 2475, 2, 1856ECtn101010.021548−1DCuttn101010.0401123−1ECtnp101010.01023717424DCuttnp101010.036232616300, 22425, 2, 1856ECtn101010.02281273−1DCuttn101010.061716−1ECtnp101010.010512572DCuttnp101010.04591132300, 35880, 2, 8970ECtn966.738461600−1DCuttn988.94113117−1ECtnp9910.0880167414DCuttnp9910.0113112012300, 35880, 2, 26910ECtn101010.06271254−1DCuttn101010.02735110−1ECtnp101010.025912622DCuttnp101010.012121183


### 4.3.5. Summary

In Table13, we finally report the best method for each group of instances from the three instance sets. For this purpose, variations including primal heuristic and using cycle-elimination cut separation are also considered. In the case a variant including a primal heuristic yields the best performance, we additionally report the best method not using primal heuristics. Formulations ECsn and ECsnh are the best formulations for almost all instances of SET-I, with the primal heuristic often yielding small improvements. The same is true for the instances of SET-II, where almost all variations of formulation EC are able to solve the considered instances in less than a second. For SET-III formulation DCut is superior for many instances with |L|=3/4·|E|, whereas EC is better for instances with |L|=1/4·|E|. In contrast to SET-I, it is beneficial to restrict the number of edges to |V|-1 as indicated with index “t”. Additionally separating cycle-elimination cuts frequently yields the overall best method, in particular for instances with |L|=3/4·|E|. Furthermore it can be observed that variants using separation of odd hole inequalities are frequently the overall best methods for this group.Table 13
Overview of all test instances from SET-I, SET-II, and SET-III and corresponding best formulations.
Set|V|d/|E||L|aBest  formulationSet-I1000.2501ECsn100ECsn, ECsnh125ECsn0.550ECsn, ECn, ECsnh100ECn, ECsnh125ECn, ECsnh0.850ECsn, ECn100ECn, ECsnh125ECsn, ECn, ECsnh2000.2100ECsn, ECsnh200ECsn250ECsn, ECsnh0.5100ECsn200ECsn250ECsn, ECsnh0.8100ECsn200ECsn, ECsnh250ECsn, ECsnhSet-II100040005EC* (several variants having same performance)10EC* (several variants having same performance)20EC* (several variants having same performance)Set-III1000.051/4·|E|Several methods having same performance3/4·|E|CEFtn0.21/4·|E|ECtñ3/4·|E|DCuttnc0.51/4·|E|ECtño3/4·|E|ECtnc0.051/4·|E|2EC* (several variants having same performance)3/4·|E|ECtñob, ECtnc0.21/4·|E|ECtñob, ECtnh3/4·|E|DCuttñobc0.51/4·|E|ECtnob3/4·|E|ECtnoc0.051/4·|E|5Several methods havingt≤03/4·|E|DCuttñc0.21/4·|E|ECtn3/4·|E|DCuttnco0.51/4·|E|ECtn, ECtnh3/4·|E|ECtnob, ECtnh10×10301EC* (several variants having same performance)50ECsnob80DCutsñob (best relaxation)20×2030ECsn, ECn50ECsn80DCuttñ (best relaxation)


## 4.3.1. MIP Formulations

In this section, we primarily focus on the comparison of formulations EC, DCut and SCF. However, particularities like node-label-constraints (3.22), or fixed number of edges (3.5), or the direct linkage of labels to edges (3.21), may significantly change the picture regarding the superiority of one method over another one. For this reason, we present the results not only for three formulations, but rather four to five variants of each formulation. Recall, that directly linking the labels to edges by (3.21) is only possible for instances with one label assigned to each edge (3.21), that is, a=1 and is generally not possible for flow-formulations. In order not to be biased towards some particular class of instances, we report these results for each of the three instance sets.Tables2 and 3 show the results for instances of SET-I with |V|=100 and |V|=200. These instances include graphs with various densities d∈{0.2,0.5,0.8}, where |E|=d·(|V|·(|V|-1)/2), and different numbers of labels, that is, |L|=1/2·|V|,|L|=|V|, and |L|=5/4·|V|. In these tables, as well as in the following ones, we report the following entities for each method and group of instances.  Columns “cnt” contain the number of instances within each group, which is 10 in most of the cases. The reason for less than ten instances reported is not being able to finish some instances with particular formulations due to high memory requirements. Columns “opt” report the number of instances that have been solved and proved to be optimal within the time limit. In columns “obj” the average objective value for all instances in the group is reported. If all instances have not been solved to optimality, this value corresponds to the average value of feasible solutions that have been found within the timelimit. Average running times in seconds are then reported in columns “t”. The average number of branch-and-bound nodes is listed in columns “bbn”, the average number of generated cuts in column “cuts”. Results of the fastest method(s) for each group are emphasized with bold letters.Table 2
Comparison of selected variants of formulations EC, DCut, and SCF on the instances from SET-I with|V|=100.
|L|=50|L|=100|L|=125dalgcntoptobjtbbncutscntoptobjtbbncutscntoptobjtbbncuts0.2EC10106.772346510109.762387610729911.212393652843ECt10106.7834719610109.72524824149911.2343769871ECtn10106.7410017310109.7118573399911.2161401402ECn10106.7024310109.7912981799911.2332648594ECsn10106.7031310109.761127349911.212257089DCut10106.780116769110109.710131437877989811.214701964611403DCutt10106.7125145895410109.7478667639199911.2740102736450DCuttn10106.72112711610109.78610217299911.211514261017DCutn10106.711909610109.75711575999911.217631861868DCutsn10106.712948910109.75111905169911.212930861536SCF1026.87028136930−110010.3720019854−19012.4720017296−1SCFt1016.77133143226−110010.37200101319−19011.77200119683−1SCFtn10106.71583−110109.767673−19911.2851033−1SCFn10106.71583−110109.763673−19911.2841033−10.5EC10103.01746510104.7374558428210105.24465307630ECt10103.0146914810104.7175503933010105.21293249382ECtn10103.09713610104.73452416510105.239452277ECn10103.002010104.78221410105.291274ECsn10103.002010104.79173410105.21137012DCut10103.02174882721084.8385815810721410105.2315093164187DCutt10103.01904652561094.7347111770624610105.2179453663175DCuttn10103.056132810104.7401113345010105.2305633342DCutn10103.027122810104.7261159751810105.22501179401DCutsn10103.027235510104.7216153939010105.22251234362SCF10103.08501475−11005.0720011453−11005.872007586−1SCFt10103.07221597−11064.7531923618−11005.5720018169−1SCFtn10103.0221−110104.7211617−110105.2171298−1SCFn10103.0201−110104.7203617−110105.2176298−10.8EC10102.01221210103.01618489810104.0999431020ECt10102.011719610103.03614217910104.01352344130ECtn10102.014410210103.0241118710104.04439483ECn10102.001010103.013210104.0171020ECsn10102.001010103.024110104.017510DCut10102.025597651093.12367244012861004.0720069583525DCutt10102.01981271311093.11997270216351094.0508363633410DCuttn10102.08771910103.031437021610104.09231193408DCutn10102.04052210103.041893245710104.07801853546DCutsn10102.03332910103.01281619310104.07402154668SCF10102.0274103−11003.672002826−11004.072002752−1SCFt10102.0335−11004.072003035−11004.072002849−1SCFtn10102.0281−110103.0292−110104.0243349−1SCFn10102.0281−110103.0292−110104.0230349−1Table 3
Comparison of selected variants of formulations EC, DCut, and SCF on the instances from SET-I with|V|=200.
|L|=100|L|=200|L|=250dalgcntoptobjtbbncutscntoptobjtbbncutscntoptobjtbbncuts0.2EC1088.03770526821662110012.97200422892230310015.472003200918669ECt1078.0454143756766510013.6720043298800710016.07200437927293ECtn10107.912961425453910213.3687860643143610114.96761462961658ECn10107.92018379510512.2514618903397310313.863871445975207ECsn10107.91918322410712.143311822378110313.96153250129158DCut1008.8720010929897110014.572003850363210018.9720036813548DCutt1009.072004392403610014.572002896286610016.1720026532622DCuttn1078.1548713056803610013.072005588476310015.7720039823552DCutn1098.0339814653863710012.97200158771220010014.97200112079494DCutsn1098.0299614937765810012.77200192801356910014.772001371210837SCF1009.372001017−110014.57200634−110016.87200559−1SCFt1008.972003204−110013.572004733−110015.872005326−1SCFtn1088.033539362−110012.472006854−110014.172004343−1SCFn1088.034988308−110012.472006468−110014.172004099−10.5EC10103.47692082691005.8720086035391006.572005380456ECt10103.4145227445581005.87200103076471006.4720090841024ECtn10103.45704696781075.5424965509081006.5720015870861ECn10103.42512611095.4129114284121086.443235771531ECsn10103.4199211095.411761465361096.440496237118DCut904.1720010867281007.272003232651007.97200272215DCutt904.372006134691007.972002982901008.27200335307DCuttn1083.551359544811006.672005573491007.47200420282DCutn1083.5313210795071006.2720017959291007.172001097564DCutsn1093.420549794121006.0720020729121006.772001432671SCF1004.37200124−11007.0720069−11007.8720054−1SCFt1003.97200207−11006.57200166−11007.37200150−1SCFtn10103.41102270−11005.77200828−11006.57200839−1SCFn10103.41204270−11005.77200749−11006.47200728−10.8EC10102.628032968161004.072001132161005.07200164048ECt10102.6304036505051004.0720021466561024.470646763757ECtn1092.7273910361310104.0503868196341094.129021331776ECn10102.67627310104.011225975110104.060933243ECsn10102.6281110104.09114845110104.03017771DCut403.072001521341008.272011051101007.172006970DCutt1003.972001511711005.272021101121006.87200111112DCuttn1033.36344142671004.672001771021005.5720012098DCutn1032.7652811034441004.272003291701004.97200158126DCutsn1062.651357992921004.072005562271005.07200226140SCF1002.9720069−11004.9720035−11005.5720033−1SCFt1022.8592354−11004.3720058−11005.1720135−1SCFtn1092.6417774−11014.06929391−11034.76712264−1SCFn1092.6418379−11014.06973375−11024.76871229−1From Tables2 and 3 we can already observe that the difficulty of solving these instances is strongly correlated to the objective function values of the instances. Higher values, in particular those larger than ten, require significantly more B&B-nodes, and the separation of more cuts. This also implies longer average running times. This property holds for all of the considered formulations. The results in Tables 2 and 3 show that formulation ECsn consistently gives the best results for these instances. The single-commodity flow formulations show a slightly better performance than the directed-cut formulations for most of the instances.The strength of the node-label-inequalities (3.22) is also demonstrated by the results in Tables 2 and 3. Their addition to the plain formulations does not only yield a significant speedup, but also enables to solve more instances regarding the set with |V|=200. The difference between Inequalities (3.22) and their extended form, given by Inequalities (3.23) is examined in Section 4.3.2. Regarding Equation (3.5) no clear conclusion can be drawn from these instances. If, however, combinations of these components are considered, the variants only using the node-label-constraints are superior in most of the cases. For formulations EC and DCut it is also possible to directly link the edges to the labels by   (3.21). In most of the cases, this yields the best results, when combined with the node-label-inequalities for both formulations, and in particular in combination with EC the overall best results.Table4 reports the results for the same formulations for the instances of SET-II. These instances have the major difference to contain only graphs of extremely low density d and just very few labels. Again, we can observe a clear superiority of formulations ECsn and ECn, which are able to solve all these instances with average running times of less than  half second.Table 4
Comparison of selected variants of formulations EC, DCut and SCF on the instances from SET-II.
|L|=5|L|=10|L|=20|V|, |E|algcntoptobjtbbncutscntoptobjtbbncutscntoptobjtbbncuts200,  800EC10103.001010105.003010107.90132ECt10103.00223610105.00831510107.9247582ECtn10103.00215710105.00624910107.9120515ECn10103.001010105.001010107.9062ECsn10103.001010105.001010107.9061DCut10103.0163810105.04146310107.914127171DCutt10103.0362610105.07183710107.918161173DCuttn10103.0042910105.0273610107.982163DCutn10103.0022410105.0064910105.00649DCutsn10103.001010105.001010107.9061SCF10103.022−110105.0932−110107.969800−1SCFt10103.032−110105.0932−110107.971800−1SCFtn10103.001−110105.013−110107.9616−1SCFn10103.001−110105.013−110107.9616−1500,  2000EC10103.501010105.902010109.90120ECt10103.53262110105.96783310109.916441129ECtn10103.52154110105.95676310109.916251385ECn10103.501010105.901010109.9080ECsn10103.501010103.501010109.9070DCut10103.5553410105.914147610109.948152184DCutt10103.51372510105.928153410109.968181144DCuttn10103.5231610105.9983310105.99833DCutn10103.5124610105.9366710109.92020139DCutsn10103.5128210105.9366010109.92019129SCF10103.5103−110105.92818−110109.9372661−1SCFt10103.5113−110105.92918−110109.9384661−1SCFtn10103.501−110105.943−110109.92020−1SCFn10103.501−110105.933−110109.91820−11000,   4000EC10104.101010106.6010101011.30130ECt10104.1201118210106.64661762101011.3121543514ECtn10104.13001382310106.623462660101011.3108262909ECn10104.101010106.6010101011.3070ECsn10104.101010106.6010101011.3060DCut10104.11654010106.64713259101011.3144191275DCutt10104.15462210106.6902036101011.3240189150DCuttn10104.1732310106.626726101011.31033647DCutn10104.112118410106.6135195101011.36426355DCutsn10104.111117810106.6476495101011.35724253SCF10104.1302−110106.69914−1101011.31243416−1SCFt10104.1312−110106.69614−1101011.31303416−1SCFtn10104.111−110106.6123−1101011.35231−1SCFn10104.111−110106.6123−1101011.34831−1In Tables5, 6, and 7, results for the instances from SET-III are reported. Table 5 shows the results for instances with |V|=100 and a=1, that is, one single label assigned to the edges. As already mentioned in Section 4.1, this instances differ from the previous ones in the way that they contain a higher number of labels, that is, r=1/4 and r=3/4 with r=|L|/|E|. It can be observed that it is beneficial to limit the number of edges to |V|-1 by (3.5) in this case. Thus, the stronger LP-relaxation implied by this restriction is beneficial in the case of higher values of r. For instances with r=1/4 formulation EC still shows the best performance, but DCut provides better results in the case of r=3/4. Hence, the strong LP-relaxation becomes even more important if |L| is in the same order of magnitude as |E|.Table 5
Comparison of selected variants of formulations EC, DCut and SCF on the instances from SET-III with|V|=100; α=1.
|L|=1/4·|E||L|=3/4·|E|dalgcntoptobjtbbncutscntoptobjtbbncuts0.05EC101019.621892172210061.67200108393124719ECt101019.6236887602610151.36480178187195559ECtn101019.6144944448610251.25760163875182801ECn101019.621491124610062.57200103413119245ECsn101019.61131396610055.57200133833151889DCut101019.6355214302610050.77200367146337417DCutt101019.6344174248710449.843817662955867DCuttn101019.612114875910649.831958715260318DCutn101019.613143794110050.47200337882315950DCutsn101019.61131396610050.47200360801343056SCF10319.65576987720−110051.572001815207−1SCFt10919.61354513872−110550.038233081605−1SCFtn101019.6315160−110849.91508800971−1SCFn101019.6499415−110050.67200894051−10.2EC10115.1709920808211736210045.172006230063102ECt101014.8675547422379010436.56326138547137549ECtn101014.8344363861674510237.16450120465121687ECn10215.363691366579492710046.072004016341557ECsn10414.848942311489506210039.272006516763256DCut10016.37200480733531610038.9720011978987861DCutt10614.83196551693714410635.837066176247626DCuttn101014.883513677869810735.824323609927852DCutn10015.77200391322970010038.572004857640239DCutsn10115.67134783395754610038.072008864573235SCF10017.0720014435−110040.5720039472−1SCFt10015.57200173479−110037.87200480980−1SCFtn10914.8240131073−110136.16495152260−1SCFn10015.2720063078−110038.4720029479−10.5EC10015.87200695543626010038.872005415355751ECt10813.32570624873042510530.740645144250552ECtn9813.21400341061876910431.050385960557375ECn10016.27200359441832310038.972002898431127ECsn10013.772002967828896210033.872006343064801DCut10015.472007645429110036.072003100819324DCutt10613.551529463903610630.343311600313285DCuttn10513.545579195854310730.23552123379780DCutn10015.472005807378510036.6720069355131DCutsn10014.4720012834815410032.47200141089913SCF10016.472001345−110034.572003160−1SCFt10014.6720019313−110032.3720035869−1SCFtn10513.547569842−110230.7584216960−1SCFn10014.572006765−110033.172002327−1Table 6
Comparison of selected variants of formulations EC, DCut and SCF on the instances from SET-III with|V|=100, a∈{2,5}.
|L|=1/4·|E|,a=2|L|=3/4·|E|,a=2|L|=1/4·|E|,a=5|L|=3/4·|E|,a=5dalgcntoptobjtbbncutscntoptobjtbbncutscntoptobjtbbncutscntoptobjtbbncuts0.05EC101016.673222327710042.87200112158123363101010.5015245210021.47200111275106501ECt101016.66311657990110735.02558113102106934101010.5036240010420.84763178547160611ECtn101016.6124707408010735.0237510217993532101010.5030635910620.63467143690125295ECn101016.621883195610042.47200116472124838101010.5015842610021.57200107718103093DCut101016.6314173240910035.17200374197286064101010.5724723810020.57200375009236293DCutt101016.63635232114101034.711267254842101010.51035030110920.510667558746230DCuttn101016.6161162787101034.76146613696101010.55115134101020.56984587025073DCutn101016.611102669410035.07200376389268567101010.539511510720.54126215290129837SCF10116.77153896512−110037.17200701281−110910.52318507224−110021.87200276624−1SCFt10716.640381339695−110135.070463581766−1101010.51580440888−110021.072001707957−1SCFtn101016.6293894−1101034.7609239014−1101010.54284−110920.52218462195−1SCFn101016.66711755−110035.87200666248−1101010.55329−110020.97200720521−10.2EC10312.3652126824011707910031.87200727206934510107.833642365853498710019.57200159231107082ECt10812.11840815984010910326.2584514156812722910107.82653987577310315.1518417149089976ECtn101011.9629420522063710326.3524211955010735810107.81281244165110315.1514013998390176ECn10712.142851660547945710034.07200498595094010107.8104156147816610019.0720011518889434DCut10013.47200434123249710027.3720072779487721017.96892706903650710016.672003335023851DCutt101011.91477178411318310725.6295755433381211057.85653677544256010414.954235580043216DCuttn101011.96815906518010925.61489249311766310107.8162815222955210614.844064462832312DCutn10013.27200395993022510027.4720031085234201077.84679654152581210015.872001576111375SCF10014.3720013282−110030.0720019389−11008.8720022933−110018.1720012399−1SCFt10012.97200105555−110027.07200320786−11008.17200107916−110015.87200109149−1SCFtn10812.1190918528−110425.9533887496−110107.8166911756−110215.1632744397−1SCFn10012.8720047542−110027.6720015439−11097.8415159801−110016.0720010494−10.5EC10011.57200982573800010028.4720093989774941016.96785101172724210014.572005051829040ECt101010.963242951526810123.46487854857100310106.9612279367859513.1380410066638284ECtn101010.950622467643210326.3524211955010735810106.925566045329613.034727258238165ECn10011.37200378581836510029.0720044406399261007.0720029141214310016.27200117516165DCut10011.872009769550310030.472001585295161007.1720011487599510015.2720057423186DCutt10011.37200130891156010822.54745958588511007.472007977621310013.8720078277958DCuttn10511.2566411813978610522.84259885084811067.150895318352910413.1574379347389DCutn10011.972007129442610027.17200473829961017.167177337317210015.2720026821652SCF10013.272001477−110026.872001628−11008.072002606−110016.27200923−1SCFt10012.1720013970−110024.3720026439−11007.672006757−110014.3720010634−1SCFtn10610.948416975−110023.4720012529−11077.042383003−110213.359236203−1SCFn10011.872009232−110025.072003000−11007.0720021470−110014.472004668−1Table 7
Comparison of selected variants of formulations EC, DCut and SCF on the grid graph instances from SET-III with|E|≈4·|V|.
|V|=10×10|V|=20×20|L|algcntoptobjtbbncutscntoptobjtbbncuts30EC10109.2420411540101011.5617496400ECt10109.2626411843101011.518375475819ECtn10109.2416391544101011.59137574231ECn10109.211369656101011.5173602200ECsn10109.211281601101011.5173558175DCut10109.261494832402211.05224623337505DCutt10109.29361964135101011.530292295619238DCuttn10109.23418921710101011.5627405810961DCutn10109.218151213641012.072003924766DCutsn10109.219135623141013.072002623113SCF10109.2815118270−110011.8720022192−1SCFt10109.264190448−110011.7720022091−1SCFtn10109.2171280−1101011.52513127−1SCFn10109.2121008−1101011.52183076−150EC9813.01018546534103610917.1434146460231132ECt9713.11959993977368710017.07200301858167539ECtn9813.015788399667834101017.03834212265107170ECn9912.91292529916378101017.0134720822111217ECsn9912.9662233913131101017.010871932138470DCut9912.986767360378737017.372002939047832DCutt9912.91032747184208810017.272003224833668DCuttn9912.9302205961290710017.072008617264236DCutn9912.933628974176137016.37200334536785DCutsn9912.920720951133237015.7720064823682SCF9013.37200368322−110018.5720013103−1SCFt9013.27200741954−110018.5720019592−1SCFtn9912.921521632−110017.17200131296−1SCFn9912.929934004−110817.15532169723−180EC10019.5720013460811837710025.07200199143139246ECt10019.9720023178920866110024.97200143214104486ECtn10019.6720022961920278710024.87200146616112030ECn10019.5720016219213890410024.67200305748138953ECsn10018.9720022816717674110024.67200299188134344DCut10018.8720025282622527310025.572003175632402DCutt10018.972002481232165139019.872002412125391DCuttn9018.7720028362522094010025.272004360444755DCutn10018.872002394891970738024.672005422662124DCutsn10018.972002489662131577025.172002526246754SCF10019.77200285092−110027.072009767−1SCFt10019.27200948572−110028.0720022180−1SCFtn10019.07200689593−110025.3720068435−1SCFn10018.87200863039−110025.2720099643−1With a single exception, the same effect can be observed for the instances witha∈{2,5} reported in Table 6. The effect of more than one label being assigned to the edges seems to make the problem easier to solve, but the effect is relatively small. It is important to note, that directly linking the labels to the edges, which was beneficial for the instances with a=1, cannot be applied to instances with larger a.Table7 shows the result for grid-graphs with 100 and 400 nodes and |L|∈{30,50,80}. The average optimal objective value on these graphs is relatively high, which makes them difficult to solve. However, all instances with |L|∈{30,50} could be solved to optimality by formulation ECsn, which showed the overall best performance on this class of instances.Having now analyzed the main variations of the discussed formulations we draw our attention to further approaches and enhancements that have been proposed in Section3.


## 4.3.2. Further Methods

In Section4.3.1 the node-label-inequalities (3.22) have been shown to be of utter importance for a strong formulation. In Section 3.3 we have also presented an extension of this idea, where two nodes are considered instead of just one. This led to the class of Inequalities (3.23). Table 8 shows a comparison of formulations ECt and DCutt with on the one hand the node-label-inequalities (3.22) and on the other hand additional Inequalities (3.23). In particular for formulation ECt these further inequalities turn out to be useful in many cases. They do not only speedup the solution process, but moreover frequently enable to solve more instances to provable optimality. However, also the opposite is often the case. It is therefore not possible to decide which approach is superior over the other based on the available data. On grid-graphs Inequalities (3.23) have not been beneficial at all.Table 8
Comparison of formulationsECt and DCutt with Inequalities (3.22), indicated with index n, and with additional Inequalities (3.23), indicated with index ñ.
ECtn/DCuttnECtñ/DCuttñ|V|,|E|,a,|L|cntoptobjtbbncutscntoptobjtbbncuts100,247,1,61101019.61449444486101019.60499492101019.6121148759101019.61915771034100,247,1,18510251.2576016387518280110750.02174657816872310649.83195871526031810549.842848676962183100,900,1,247101014.83443638616745101014.8177183526741101014.8835136778698101014.819492697316494100,900,1,74210237.1645012046512168710735.82403480384539810735.82432360992785210835.718222052215153100,2475,1,61810813.2140034106187699813.21801464692236310513.545579195854310413.65417107739933100,2475,1,185610431.05038596055737510730.32506272412495710730.2355212337978010830.2290737153689100,247,2,61101016.61247074080101016.61601498101016.6161162787101016.6211348907100,247,2,18510735.0237510217993532101034.7932693274101034.76146613696101034.71914251226100,900,2,247101011.96294205220637101011.99125510620864101011.968159065180101011.915231643512011100,900,2,74210326.3524211955010735810725.83265696855378510925.61489249311766310925.615831707612240100,2475,2,618101010.9506224676432101010.955837153392110511.2566411813978610111.770501250311444100,2475,2,185610423.25213619085329410323.25757731455765710522.842598850848110822.5364941854254100,247,5,61101010.50306359101010.50248306101010.55115134101010.511316321100,247,5,18510620.6346714369012529510920.512026057149983101020.56984587025073101020.54983677420977100,900,5,24710107.81281244165110107.82883932482510107.816281522295521057.856756649942125100,900,5,74210315.15140139983901769415.043441555897319810614.84406446283231210414.951715043438692100,2475,5,61810106.9255660453210106.9624279367851067.15089531835291007.4720083036431100,2475,5,185610613.03472725823816510613.038481036354165110413.157437934738910113.671918419861710×10,360,1,3010109.241639154410109.262641184310109.2341892171010109.2906196413510×10,360,1,509813.0157883996678349813.01877102421756929912.930220596129079912.91034747184208810×10,360,1,8010019.6720022961920278710019.9720025195722694110018.772002836252209409018.8720028328824139920×20,1520,1,30101011.59137574231101011.517675475819101011.5627405810961101011.52866229561923820×20,1520,1,50101017.0383421226510717010117.0719432605117805810017.07200861726423610017.27200347423577920×20,1520,1,8010024.8720014661611203010024.9720015052911012010025.27200436044475510020.672002571826997Further formulations, considered in Section3, are based on the property that a tree must not contain a cycle by definition. Formulation MTZtn requires just a polynomial number of variables, but contains constraints with infamous “Big-M” constants, as the SCF formulation does. On the contrary CEF contains an exponential number of Inequalities (3.15), which need to be separated as cutting-planes as for the DCut or EC formulation. Due to their fast separation by a simple shortest-path computation, other formulations may benefit from additionally using cycle-elimination cuts. Corresponding results are reported in Table 9, column “cec” lists the average number of separated cycle-elimination cuts. Whereas MTZtn and CEFtn show a relatively weak performance on the instances with r=1/4, they provide good results in the case of r=3/4. In particular, for the low-density graphs CEFtn could solve all instances to optimality, which no other method was able to do. For the dense graphs best results are obtained by DCuttnc and ECtnc.Table 9
Comparison of various formulations based on cycle elimination, that is, the Miller-Tucker-Zemlin formulation MTZ and the CEF on the instances from SET-III with|V|=100, a=1. Furthermore results for connectivity-based formulations (EC and DCut), enhanced by cycle elimination inequalities are reported.
|L|=1/4·|E||L|=3/4·|E|dalgcntoptobjtbbncutsceccntoptobjtbbncutscec0.05MTZtn10519.73931502063−1−110749.93112721279−1−1CEFtn10619.63000135407−116638101049.890194205−16389CEFtñ10519.63998155632−11764210749.92208208113−114321ECnc101019.61413531215910050.372005328361707981783ECtnc101019.6129151539610749.8256662656446075502DCutnc101019.61314339315510050.472003766493512881630DCuttnc101019.61310297009410749.82291367452774828590.2MTZtn10715.0427645276−1−110535.8427287003−1−1CEFtn10714.9321736913−1329810735.7231391215−15422CEFtñ10315.2530761399−1569010735.7266840566−12478ECnc10015.672003183514311810037.8720059337153330ECtnc101014.87011068719667010835.7187151079155443426DCutnc10015.97200392252975517110039.4720047294392063DCuttnc101014.873711214721258110835.71537217211379514000.5MTZtn10513.555557818−1−110330.9565813851−1−1CEFtn10513.650388686−176310730.1444419156−11653CEFtñ10313.657918399−1106310530.555706646−1711ECnc10014.172003463263510032.77200649711825ECtnc10713.53865877211691310930.1211291201344665DCutnc10015.67200535333952410038.27200696453576DCuttnc10813.533947452643367510930.0242774755918576Table10 shows the results that have been obtained by including primal heuristics into the branch-and-bound algorithm. Formulations ECtn, ECsn, DCuttn, and DCutsn are considered for this purpose. As indicated by preliminary experiments it turned out to be advantageous only to use the primal heuristics in the root node, as they were generally not able to find improved solutions based on the information provided by the LP-solution in other B&B-nodes. Embedding MVCA in B&B has a positive effect w.r.t. the variants “tn” of formulations EC and DCut, but a negative impact concerning variants “ts”.Table 10
Comparison of best formulations used without and with primal heuristics, that is, MVCA and ACO.
|L|=1/4·|E||L|=3/4·|E|dalgcntoptobjtbbncutscntoptobjtbbncutsECtn101019.6144944448610251.257601638751828010.05ECsn101019.61131396610055.57200133833151889DCuttn101019.612114875910649.831958715260318DCutsn101019.610133689510649.831958715260318ECtn+MVCA101019.6125474486610251.35771145352166307ECsn+MVCA101019.621635125510052.37200137776154933DCuttn+MVCA101019.611105671410649.829025728241009DCutsn+MVCA101019.612153099310050.47200371927343330ECtn+ACO101019.612442539168449.63600107155110775ECsn+ACO101019.62133997810049.97200134930151941DCuttn+ACO101019.6109376279449.840197450652846DCutsn+ACO101019.611130382810050.47200371927343330ECtn101014.8344363861674510237.164501204651216870.2ECsn10414.848942311489506210039.272006516763256DCuttn101014.883513677869810735.824323609927852DCutsn101014.883513677869810038.072008864573235ECtn+MVCA101014.8767524962853110236.96004120042120862ECsn+MVCA10414.849042122228987310038.772006330860554DCuttn+MVCA101014.879912503828410835.721693421925835DCutsn+MVCA10115.57067726585489410038.172008257567712ECtn+ACO101014.834531157143139536.041356736266292ECsn+ACO10314.953232282739441010036.172006434060405DCuttn+ACO101014.86401103471499635.825243556026632DCutsn+ACO10215.06977807255492510036.272008355369016ECtn9813.21400341061876910431.0503859605573750.5ECsn10013.772002967828896210033.872006343064801DCuttn10513.545579195854310730.23552123379780DCutsn10014.4720012834815410730.23552123379780ECtn+MVCA10813.31991404402399510530.542745320250948ECsn+MVCA10013.772002798957963310032.472006702666888DCuttn+MVCA10713.333216462585210930.0272884797236DCutsn+MVCA10014.3720011154722410032.272001487810082ECtn+ACO9713.3226144962257186231.354196148159297ECsn+ACO10013.772003453588005410031.172006446963099DCuttn+ACO10713.43534765969338530.53374105778304DCutsn+ACO10013.8720012035731910031.27200139199175


## 4.3.3. Odd hole Inequalities

We now draw our attention to the odd hole inequalities. Within preliminary tests, we determined a tight timelimit of 10−3 seconds for solving the MIP (3.26)–(3.38) to show a generally good performance. Two algorithmic variants are considered for the results reported in Table 11. The first version (denoted with index o) simply adds the found valid cutting-planes to the MIP. Alternatively, the set of labels corresponding to the obtained odd hole can also be used to deduce a branching rule. This was motivated by the observation that many lifted odd hole cutting planes, found by MIP (3.26)–(3.38), were not strong enough to define facets w.r.t. the involved label variables. As a consequence, these variables remained fractional after the cutting-plane was added to the MIP. However, odd holes provide important information and references to situations where special configurations of label-variables artificially reduce the LP-relaxation. Hence it is likely that immediately branching over these variables may be beneficial. This is done by inserting all labels of the odd hole into a global queue, and always branch over such a variable unless the queue is empty. Index ob denotes this approach in Table 11. Odd hole cuts are separated with lowest priority amongst the user-defined cutting-planes, and are only separated in levels of the B&B-tree which are multiples of ten.Table 11
Comparison of formulationsECt and DCutt with and without using odd hole ienqualities. Index o denotes if odd hole inequalities are separated, index b indicates that odd hole inequalities have been used to induce branching over related label variables.
ECtn/DCuttnECtno/DCuttnoECtnob/DCuttnob|V|,|E|,a,|L|cntoptobjtbbncutsoptobjtbbncutsohoptobjtbbncutsoh100,247,1,61101019.614494444861019.62556925141231019.6175226470119101019.61211487591019.613116377211019.61311217331100,247,1,18510251.25760163875182801251.25760144151159964194251.1576014356215932117310649.831958715260318649.83214833475832211649.83197859976058513100,900,1,247101014.834436386167451014.841737993182841341014.83433463915817120101014.88351367786981014.889214659936411014.898715816101312100,900,1,74210237.16450120465121687336.863771268191289241251236.76007119218119667130810735.824323609927852735.82369347172634877735.82371337572608361100,2475,1,61810813.214003410618769813.324994859928883174813.31820354792177513810513.5455791958543713.54261830576159713.34318832277698100,2475,1,185610431.050385960557375530.841335307952191709431.04499549455425461410730.23552123379780930.028278780680951930.027788061689839100,247,2,61101016.612470740801016.61451484496231016.6134987436320101016.61611627871016.617116178801016.61611467751100,247,2,18510735.0237510217993532635.13485137028125999272735.0243110259590520178101034.761466136961034.7695073408181034.722175816304100,900,2,247101011.96294205220637912.099748954228661371011.98574193321903129101011.9681590651801011.98918242686861011.910008936773411100,900,2,74210326.35242119550107358326.253951184831043411312426.3484110707294593122010925.614892493117663925.61603241121803182925.61443238371680167100,2475,2,618101010.95062246764321010.9748289179107441010.93881777036841410511.25664118139786511.257361095894677611.157271115593168100,2475,2,185610423.252136190853294123.864907452564822822223.56298722566205975410522.8425988508481722.636427480707322822.534797831717320100,247,5,61101010.503063591010.5030635911010.512673381101010.551151341010.5511513401010.551151340100,247,5,18510620.63467143690125295420.74461157779137051937620.63047116829103068673101020.56984587025073920.5787438832492112920.5783451442557510100,900,5,24710107.812812441651107.8134125216312107.815713710862310107.81628152229552107.815131507192221107.815401515393650100,900,5,74210315.1514013998390176415.0483813275683094702415.044581256657832765110614.844064462832312514.94520458183317222514.94392444353226718100,2475,5,61810106.92556604532106.925365815190106.9262670157701067.150895318352967.0509255033685067.05093544736080100,2475,5,185610613.034727258238165712.931326247333275255712.92343501062408715810413.1574379347389313.36505889684209313.1621382597770810×10,360,1,3010109.2416391544109.251427135010109.25142713841110109.23418921710109.232168515105109.23417111576610×10,360,1,509813.015788399667834813.015508111266089310912.961954900424881459912.93022059612907912.9387251421618023912.92981993812261810×10,360,1,8010019.67200229619202787019.872002119031868851086019.57200211561188812110210018.77200283625220940018.87200232626190432403019.0720022397018883238120×20,1520,1,30101011.591375742311011.51073749431001011.5106379942490101011.56274058109611011.575340281156701011.5705411211261020×20,1520,1,50101017.03834212265107170917.0423220992310575532917.043242100031073853910017.072008617264236017.0720077221606036017.072008045359244420×20,1520,1,8010024.87200146616112030024.87200133250102086626024.9720013164110147957710025.272004360444755025.27200392624170421025.27200394514295219The results in Table11 show that the odd hole inequalities are beneficial in many cases, in particular when used to deduce branching rules from the corresponding label-variables. For instances from SET-I and SET-II, almost no odd holes have been found with the described parameter settings. For dense graphs it is less likely to find odd holes that are violated by the current LP-solution, as each node is incident to many edges. Hence |L(v)| is in the same order of magnitude as |V| in the expected case. This implies many nonzero lifting coefficients in Inequalities (3.25), reducing the chance of finding a valid inequality that is actually violated by the current LP-solution. Hence, the separation of odd hole inequalities is most beneficial for sparse graphs. Also the number of labels compared to the number of edges has an impact on the efficiency of the odd hole separation. If the number of labels is relatively low, the expected label frequency νl will be high. This implies high values for the lifting coefficients γl, which in turn reduces the chance of finding violated odd hole inequalities. If, on the other hand, the number of edges is too high, odd holes are generally less likely to occur, as the sets L(v)∩L(u), for all v,u∈V can be expected to be very small or even empty.


## 4.3.4. Branch-and-Cut-and-Price

Additionally, using the column generation approach within the B&C framework, that is, branch-and-cut-and-price (BCP) is only beneficial for a very special class of instances. For most of the instances almost all variables are priced in during the solution process. The computational overhead for solving the pricing problem and resolving the MIP implies significantly higher running times in this case. However, if the instances consist of a high number of labels, and have an optimal solution that is significantly lower than the average optimal solution value when assigning the labels to the edges randomly in the instance construction process, BCP shows a superior performance. To study this effect, special instances have been created containing single optima having a relatively low number of labels. The computational results for these instances are reported in Table12. In particular for the larger instances a clear superiority of the BCP approach w.r.t. the corresponding B&C algorithm can be observed. For this special class of instances, the percentage of created label variables is always less than 30% of the total number of labels (reported in column “priced”). Although the importance of such instances may be quite limited for many purposes, the instances used for the data compression approach presented in [17] exhibit comparable properties. For the data-compression application presented therein, the BCP approach is thus a valuable and important mean for exactly solving large instances.Table 12
Branch-and-cut-and-price results for a special class of instances containing many labels and isolated optima with a relatively low number of labels.
|V|,|E|,a,|L|Methodcntoptobjtbbncutspriced100, 247, 2, 61ECtn10105.00132−1DCuttn10105.0017−1ECtnp10105.0016414DCuttnp10105.0011317100, 247, 2, 185ECtn101010.0011−1DCuttn101010.0012−1ECtnp101010.001211DCuttnp101010.00137100, 900, 2, 247ECtn10105.00130−1DCuttn10105.01115−1ECtnp10105.0017229DCuttnp10105.0021928100, 900, 2, 742ECtn101010.001442−1DCuttn101010.081325−1ECtnp101010.0249732830DCuttnp101010.012324125100, 2475, 2, 618ECtn10105.01246−1DCuttn10105.019415−1ECtnp10105.0165127DCuttnp10105.01141926100, 2475, 2, 1856ECtn101010.021548−1DCuttn101010.0401123−1ECtnp101010.01023717424DCuttnp101010.036232616300, 22425, 2, 1856ECtn101010.02281273−1DCuttn101010.061716−1ECtnp101010.010512572DCuttnp101010.04591132300, 35880, 2, 8970ECtn966.738461600−1DCuttn988.94113117−1ECtnp9910.0880167414DCuttnp9910.0113112012300, 35880, 2, 26910ECtn101010.06271254−1DCuttn101010.02735110−1ECtnp101010.025912622DCuttnp101010.012121183


## 4.3.5. Summary

In Table13, we finally report the best method for each group of instances from the three instance sets. For this purpose, variations including primal heuristic and using cycle-elimination cut separation are also considered. In the case a variant including a primal heuristic yields the best performance, we additionally report the best method not using primal heuristics. Formulations ECsn and ECsnh are the best formulations for almost all instances of SET-I, with the primal heuristic often yielding small improvements. The same is true for the instances of SET-II, where almost all variations of formulation EC are able to solve the considered instances in less than a second. For SET-III formulation DCut is superior for many instances with |L|=3/4·|E|, whereas EC is better for instances with |L|=1/4·|E|. In contrast to SET-I, it is beneficial to restrict the number of edges to |V|-1 as indicated with index “t”. Additionally separating cycle-elimination cuts frequently yields the overall best method, in particular for instances with |L|=3/4·|E|. Furthermore it can be observed that variants using separation of odd hole inequalities are frequently the overall best methods for this group.Table 13
Overview of all test instances from SET-I, SET-II, and SET-III and corresponding best formulations.
Set|V|d/|E||L|aBest  formulationSet-I1000.2501ECsn100ECsn, ECsnh125ECsn0.550ECsn, ECn, ECsnh100ECn, ECsnh125ECn, ECsnh0.850ECsn, ECn100ECn, ECsnh125ECsn, ECn, ECsnh2000.2100ECsn, ECsnh200ECsn250ECsn, ECsnh0.5100ECsn200ECsn250ECsn, ECsnh0.8100ECsn200ECsn, ECsnh250ECsn, ECsnhSet-II100040005EC* (several variants having same performance)10EC* (several variants having same performance)20EC* (several variants having same performance)Set-III1000.051/4·|E|Several methods having same performance3/4·|E|CEFtn0.21/4·|E|ECtñ3/4·|E|DCuttnc0.51/4·|E|ECtño3/4·|E|ECtnc0.051/4·|E|2EC* (several variants having same performance)3/4·|E|ECtñob, ECtnc0.21/4·|E|ECtñob, ECtnh3/4·|E|DCuttñobc0.51/4·|E|ECtnob3/4·|E|ECtnoc0.051/4·|E|5Several methods havingt≤03/4·|E|DCuttñc0.21/4·|E|ECtn3/4·|E|DCuttnco0.51/4·|E|ECtn, ECtnh3/4·|E|ECtnob, ECtnh10×10301EC* (several variants having same performance)50ECsnob80DCutsñob (best relaxation)20×2030ECsn, ECn50ECsn80DCuttñ (best relaxation)


## 4.4. Comparison to Other Work

In this section, we present direct comparisons to existing work, in particular [16]. Table 14 shows the results presented in [16], running times have been rounded to integers. Formulation “MLSTb” corresponds to formulation SCF of this work. Formulation “MLSTc” only uses a weaker coupling of labels to edges, given by the following inequalities:(4.1)∑(i,j)∈Axij≤min⁡{|V|-1,A(l)}zl,∀l∈L.
Table 14 furthermore reports results for the implementation of the exact backtracking method from [1], labelled with “MLST-CL”. Table 15 shows the running times of selected MIP variants in comparison to our reimplementation of the flow formulation “MLSTb” from [16] (SCF). Formulation ECtn is clearly superior to the others, all instances have been solved in less than one second. Higher running times of SCF as opposed to “MLSTb” can be explained due to the fact that the SCIP framework [26] has been used for the implementation of SCF whereas “MLSTb” has been implemented with the ILOG CONCERT framework [27].Table 14
Running times in seconds reported in [16], rounded to integers.
l510205102051020n2050100MLSTb000001013MLSTc000001017MLST-CL000000001l510205102051020n2005001000MLSTb031519136243621MLSTc163443837151321994MLST-CL006007100360l510205102051020n2050———MLSTb0001098———MLSTc000694———MLST-CL0004500———Table 15
Running times for instances that have been created according to specification from [16]. The first column lists the method for the corresponding row. In parenthesis the corresponding method from [16] is reported.
l510205102051020n2050100avg (|LT|)2.02.53.82.43.35.03.04.16.6SCF (MLSTb)0000000019SCFtn000000001DCuttn000000001ECtn000000000ECsn000000000A* (MLST-CL)000000001l510205102051020n2005001000avg (|LT|)3.05.07.93.55.99.94.16.611.3SCF (MLSTb)339712938431961303SCFtn016041911351DCuttn0041321121367ECtn000000000ECsn000000000A* (MLST-CL)00130015900609d0.20.50.80.20.50.8———n2050———avg (|LT|)7.13.52.23.03.97.6———SCF (MLSTb)000234025———SCFtn000301———DCuttn000522———ECn000000———ECsn000000———A* (MLST-CL)0006700———Table16 shows the results of selected MIP variants in comparison to the exact A* backtracking-search procedure used in [12]. The A*-algorithm is very effective for instances with small optimal objective value, but instances with larger objective values or large sets of labels cannot be solved. The time limit imposed by the authors of [12] was three hours. It is important to note that the running times listed in Table 16 are not directly comparable, as the authors of [12] list the computation time at which the best solution was obtained, and also different hardware has been used. For some groups, where A* could not solve all instance (indicated by “NF”), the MIP method was able to do so. Furthermore, it is reported if the MIP method could solve some but not all instances within some group. In any case the average objective value for the ten instances of each group is reported in column “avg(|LT|)”, also considering the best feasible solutions that have been found within the time limit of two hours. If all instances have not been solved to optimality, this is indicated with “(*)” in this particular columns.Table 16
Comparison to results reported in [12] for the A*-algorithm. Columns MLSTECn list the average total running times for each group of this particular MIP in seconds, columns A* list the running times in seconds (rounded to integers) reported in [12], at which the best solution was found.
|V||L|davg (|LT|)A*MLSTECtnopt|V||L|davg (|LT|)A*MLSTECtnopt100250.81.800104001000.82.0n/a6010100250.52.000104001000.52.2n/a6110100250.24.500104001000.25.8 (*)n/aNF8100500.82.000104002000.83.0n/a81710100500.53.000104002000.5NAn/aNANA100500.26.7100104002000.29.3 (*)n/aNF01001000.83.002104004000.8—n/aNF01001000.54.729104004000.56.2 (*)n/aNF01001000.29.7NF6104004000.214.6 (*)n/aNF01001250.84.0017104005000.8—n/aNF01001250.55.218011104005000.57.3 (*)n/aNF01001250.211.0NF12104005000.217.1 (*)n/aNF0200500.82.003105001250.82.0015710200500.52.202105001250.52.6019610200500.25.2510105001250.26.3 (*)NFNF22001000.82.6028105002500.83.052192102001000.53.4019105002500.54.3 (*)NFNF12001000.27.9NF191105002500.210.3 (*)NFNF02002000.84.023911105005000.84.8 (*)NFNF02002000.5—NFNF95005000.56.9 (*)NFNF02002000.2—NFNF75005000.216.4 (*)NFNF02002500.84.021301105006250.85.1 (*)NFNF02002500.5—NFNF95006250.58.4 (*)NFNF02002500.2—NFNF35006250.219.0 (*)NFNF0In general, it can be observed that relatively small instances could be solved efficiently by the MIP approach, but, for larger instances with|V|=400 and |V|=500, it generally fails to produce provable optimal solutions within the allowed time limit.


## 4.5. Summary

For all formulations, the node-label-constraints (3.22) significantly improved running times and reduced the number of branch-and-bound nodes. Despite its relatively poor LP-relaxation, formulation ECtn turned out to be superior to the other ones for a broad class of test instances, which is mainly to the fast cut separation and the low number of involved variables. Amongst the other considered formulations, DCuttn is superior to ECtn for dense graphs with a huge number of labels.The odd hole cuts (3.25) significantly improved running times and number of branch-and-bound nodes for some classes of instances, in particular when branching rules are deduced from the label sets corresponding to the found odd holes. Using BCP for dynamically adding new labels during the solution process turned out to be beneficial only in the case where the input instances significantly deviate from random label assignments, that is, where the optimal solution is much lower than the expectation value of randomly assigned labels. However, such solutions may likely easily be found also by heuristic methods. Nevertheless, this could remain the only way to prove optimality for “easy” large-scale instances.


## 5. Conclusions

In this work we presented a branch-and-cut- (and-price) framework for solving MLST instances exactly. We gave a comparison of an underlying flow-formulation in comparison to the (better) directed cut-based formulations, which has been applied for the MLST problem for the first time. Furthermore, a new connectivity formulation permitting a fast cutting-plane separation has been presented. We further introduced new valid inequalities to strengthen the formulations and the application of odd hole inequalities to this problem. To separate cutting-planes based on these odd hole inequalities, a new separation heuristic based on a mixed integer program using Miller-Tucker-Zemlin inequalities has been proposed.Moreover, a detailed theoretical and computational comparison of the contribution of the presented algorithmic building blocks has been presented. Our results show that the presented framework is able to solve small- to medium-sized instances to optimality within a relatively short amount of time. Existing benchmark instances could be solved within a significantly shorter computation time than before, and new (larger) instances could be solved to proven optimality for the first time.



---

*Source: 143732-2011-06-22.xml*