In many real-world routing problems, decision makers must optimise over sparse graphs such as transportation networks with non-metric costs on the edges that do not obey the triangle inequality. Motivated by finding a suficiently long running route in a city that minimises the air pollution exposure of the runner, we study the Prize-collecting Travelling Salesperson Problem (Pc-TSP) on sparse graphs with non-metric costs. Given an undirected graph with a cost function on the edges and a prize function on the vertices, the goal of Pc-TSP is to ifnd a tour rooted at the origin that minimises the total cost such that the total prize is at least some quota. First, we introduce heuristics designed for sparse graphs with non-metric cost functions where previous work dealt with either a complete graph or a metric cost function. Next, we develop a branch & cut algorithm that employs a new cut we call the disjoint-paths cost-cover (DPCC) cut. Empirical experiments on two datasets show that our heuristics can produce a feasible solution with less cost than a state-of-the-art heuristic from the literature. On datasets with non-metric cost functions, DPCC is found to solve more instances to optimality than the baseline cutting algorithm we compare against.
3) m g ( e d i x o i d n e g o r t i N industry and construction largely contribute to poor air quality [10]. Fortunately, recent advances in air quality modelling [11] means live, localised air quality forecasts can be used to predict the air pollution exposure on individual streets (see Section 5). Secondly, the runner requests the route starts and ends at the same location and is suficiently long. For example, the runner may ask for a route that starts and ends at their home and is at least 5km. Finally, the runner asks that the route is not repetitive: whilst running up and down a single street with good air quality many times is an efective way to minimise air pollution exposure, it is also a very boring route for the runner. We add the constraint that no section of the route is repeated, leaving other constraints on route repetition to future work.
Our motivating example can be formulated as an instance of Pc-TSP. The road network is represented by an undirected graph where the edges are roads and vertices are intersections. The road network is a sparse graph: the number of edges is at most where is a constant and is the number of vertices. The start and end location of the route is represented by a root vertex. The air pollution exposure on a road can be modelled by a non-metric cost function on the edges. The length of the runner’s route is analogous to prize collected on vertices by the salesperson: the prize is generated by splitting each edge (, ) in the graph into two edges (, ), (, ) and assigning the length of edge (, ) to the prize of a newly created vertex , whilst the prize of and is zero. To avoid route repetition, we ask that the route is a simple cycle. The objective is to minimise the air pollution exposure of a simple cycle starting and ending at the root vertex such that the length of the route is at least the given quota.
From the polyhedral results derived by Balas [6, 12, 13], three papers propose exact algorithms for Pc-TSP [7, 14, 15]. Fischetti and Toth [7] derive lower bounds, however, experimental results on randomly-generated, directed, complete graphs show instances with a symmetric cost function (which is equivalent to a cost function over undirected edges) could not be solved on graphs with greater than 40 vertices due to excessive computing time. Both [14] and [15] use cutting planes to strengthen the lower bound via valid inequalities (constraints that do not eliminate any feasible integer solutions) and conditional inequalities [16] (constraints that are valid for every optimal solution but not for every feasible solution). Given an upper bound on the optimal solution, cost-cover inequalities are a type of conditional inequality for Pc-TSP that constrain vertex variables using the cost of connecting a set of vertices. The cost-cover inequalities of [14] and [15] both assume the cost function is metric. Moreover, the heuristics used in [14] and [15] to obtain the upper bound assumes the graph is complete.
There are some key diferences when designing polynomial-time heuristics for Pc-TSP on complete graphs with metric costs versus sparse graphs with non-metric costs. First, given an instance of Pc-TSP on a complete graph, one can construct a feasible solution [14, 15, 17] in polynomial time; but when the graph is incomplete, we prove in Proposition 2 that no polynomial-time algorithm is guaranteed to recover a feasible solution to every instance of Pc-TSP, unless = . Second, given a tour whose prize is less than the quota, heuristics [18, 19] for complete graphs increase the prize by adding a vertex between two adjacent vertices ℎ, ℎ+1 in until the tour has suficient prize; however, on sparse graphs, one cannot assume edges (ℎ, ) and (, ℎ+1) always exist. Lastly, given tour whose prize is at least the quota, heuristics from the literature decrease the cost whilst maintaining feasibility by applying operations such as deleting a vertex [18], replacing a vertex [20, 17], or re-sequencing the tour [19]; similarly to above, these operators assume the existence of edges that may not exist in a sparse graph. Moreover, [19] explicitly assumes the cost function is metric in their re-sequencing operator. We conclude our literature review by emphasising that constructing a complete graph ′ from our sparse input graph then naively running a heuristic from the literature on ′ does not guarantee the solution returned by the heuristic will be feasible for . Furthermore, such a construction increases the number of edges to (2), slowing down the running time. We give two constructions in Appendix A of the supplementary material.
Contributions With the motivation of finding routes minimising air pollution exposure in mind, the focus of this paper is to develop algorithms to solve Pc-TSP on sparse, undirected graphs with non-metric cost functions. Our contributions are: 1. Proposing a three-stage heuristic called Suurballe’s path extension & collapse (SBL-PEC) which (i) generates an initial low-cost tour; (ii) increases the prize of the tour by adding paths with the smallest cost-to-prize ratio; and (iii) decreases the cost of the tour whilst maintaining feasibility by swapping a sub-path of the tour for an alternative path with less cost. Stages (ii) and (iii) contain [19] as a special case. 2. Deriving a new disjoint-paths cost-cover inequality and proving it is stronger than a shortest-path cost-cover inequality (Proposition 4). Our disjoint-paths cost-cover inequality is integrated into our branch & cut algorithm for solving instances to optimality. 3. Empirically evaluating our method on real-world instances from the London air quality dataset [11] and on synthetic instances from TSPLIB [21]. We compare our heuristics against [19] and compare our branch & cut algorithm against an adaptation of [14].
An instance of Pc-TSP is given by the tuple ℐ = (, , , , 1). The graph is undirected with vertices () and edges (). The graph is assumed to be connected and simple with no self-loops. The number of vertices and the number of edges are denoted = | ()| and = |()| respectively. The set of neighbours of vertex is denoted () = { ∈ () : (, ) ∈ ()}. The cost function : () → N0 defined on the edges is non-negative where N0 = N ∪ {0}. The prize function : () → N0 defined on the vertices is also non-negative. For convenience, we denote the total prize of a set of vertices ⊆ () as () = ∑︀∈ (). Similarly, the total cost of a set of edges ⊆ () is ( ) = ∑︀(,)∈ (, ). We are given a non-negative quota ∈ N0. The root vertex is 1 ∈ (). Definition 1. A tour = (1, . . . , , 1) of an undirected graph is a sequence of adjacent vertices such that each vertex in the tour is visited exactly once. A vertex is visited exactly once if the tour enters exactly once and leaves exactly once. The set of vertices in the tour is defined by ( ) = {1, . . . , } and the set of edges of the tour is defined by ( ) = {(1, 2), . . . , (− 1, ), (, 1)}. We say a tour is prize-feasible if ( ( )) ≥ .
vertex 1 such that is prize-feasible. The objective of Pc-TSP is to minimise the total cost (( )) of for all feasible tours we have (( ⋆)) ≤ (( )). the edges in a tour such that the tour is a feasible solution. A tour ⋆ is an optimal solution to ℐ if
A graph is sparse if the number of edges is at most , where is a positive constant. and the cost function is non-metric otherwise.
Let be the least-cost path from vertex to vertex in and let () be the set of path edges. An edge (, ) is metric if ∀ ∈ (): (i) (, ) = 0 ⇔ = , (ii) (, ) = (, ), (iii) (, ) ≤ (()) + (()). A cost function is metric if edge (, ) is metric for ∀(, ) ∈ (), The number of metric edges in () is at least − 1.
Lemma 1. Let be a connected, undirected graph and : () → N0 be a cost function on the edges.
Given graph and cost function : () → N0, the metric surplus (, ) is: (, ) = ︁( ∑︀ (,)∈() (, ) − ( − 1)
︁) − ( − 1) where (, ) = 1 if edge (, ) is metric, or 0 otherwise.
In this paper, we assume the input graph is sparse and we do not assume the triangle inequality (iii) in Definition 3 always holds for the cost function. The metric surplus from Definition 4 gives us a measure of “how metric” a cost function is. Notice that if all edges in are metric, then (, ) = 1. But if the number of metric edges is equal to the lower bound − 1 from Lemma 1, then (, ) = 0. Finally, given an instance ℐ, we apply pre-processing to reduce the size of a sparse input graph by removing vertices that are not in the same biconnected component as the root vertex 1 (see Appendix B.2).
Heuristics for Pc-TSP provide an upper bound on the optimal solution. A heuristic that runs eficiently in worst-case polynomial-time complexity is desirable. However, on a general graph which is not guaranteed to be complete, the design of polynomial-time heuristics that always return a prize-feasible tour (if one exists) is not possible: guaranteed to find a feasible solution (if one exists) for every instance of Pc-TSP.
Proposition 2. Assume ̸= . Let be any undirected graph. No polynomial-time algorithm is Proof. Reduction from Hamiltonian Cycle: see Appendix C.
Whilst the polynomial-time heuristics we design in this section are not guaranteed to always find a feasible solution on all general input graphs due to Proposition 2, our aim is to design heuristics that ifnd a low-cost feasible solution on
most sparse, non-metric instances in practice. This section presents a combined heuristic (Section 3.4) comprising of three distinct components: generating a starting solution (Section 3.1); increasing the prize of the tour (Section 3.2); and reducing the cost of the tour (Section 3.3). 3.1. Suurballe’s Heuristic then appending the modified
2 to the end of 1.
To find an initial low-cost tour, we propose Suurballe’s heuristic (SBL). The central idea is to find tours 1, . . . , − 1 from the least-cost pair of vertex-disjoint paths from the root vertex 1 to every other vertex ∈ ()∖{1}. Two simple paths 1 = (1, . . . , ), 2 = (1, . . . , ) from 1 = 1 = 1 to = = are vertex disjoint if (1) ∩ (2) = {1, }. In an undirected graph, 1 and 2 .
9
Path Extension (β =3, i=1) 0 tour old path extension 1 2 1 8 1
1
L(X hβ ) = -3
L¯ = -3
(a) Suurballe’s heuristic generates the initial tour (b) Path extension of Fig. 2a with = 3 finds a tour
is 6. We set ⋆ ←
(
prize-feasible, it returns the tour that maximises the prize. Suurballe’s algorithm1 [22] for finding the least-cost pair of vertex-disjoint paths from 1 to every other vertex takes ( log ). Checking a single tour is prize-feasible takes () and the heuristic checks − The overall running time of our algorithm is ( log + 2). On a sparse graph, the worst-case is dominated by (2). On a dense graph, the worst-case is dominated by ( log ). The weakness of SBL is it fails to find a prize-feasible tour if there does not exist a least-cost pair of vertex-disjoint paths 1 tours for prize-feasibility. 1, 2 from 1 to some ∈ () such that ( (1)) + ( (2)) − () ≥ . 3.2. Path Extension Given an initial tour = (1, . . . , , 1) with 1 = 1, we propose a path extension algorithm to increase the total prize of the tour. Increasing the prize has two goals: first, if is not prize-feasible, then increase the prize to obtain feasibility; second, if is prize-feasible, then explore the solution space in diferent areas of the graph by increasing the prize. Intuitively, in each iteration , the algorithm searches for possible extension paths between two vertices of the tour, then chooses the extension path with the smallest cost-to-prize ratio. A new tour with larger prize is constructed from the extension path and the existing tour. The algorithm repeatedly increases the prize of the tour with extension paths until a termination criteria is met.
extension path ℎ from ℎ to ℎ+ where ∈ N is a step size parameter and = | ( )|. The extension path ℎ is not allowed to use vertices in except for ℎ and ℎ+ . To find ℎ , we use a Breadth First Search (BFS) from ℎ such that | ( ℎ )| ≥
3. Let us define the internal path ℎ = (ℎ, ℎ+1, . . . , ℎ+ )
to be the sub-path of that would be replaced by the extension path ℎ . A new tour can be created by
replacing the internal path with the extension path. To compare extension paths, we propose a ratio of
the cost to prize called the unitary loss:
( ℎ ) =
(( ℎ )) − (( ℎ ))
( ( ℎ )) − ( ( ℎ ))
where ( ( ℎ )) > ( ( ℎ ))
(
In each iteration , we construct a set = {ℎ |( ( ℎ )) > ( (ℎ )), ℎ ∈ {1, . . . , − }} of possible extension paths that have more prize than the internal path. Note we exclude from extension paths ℎ for which ℎ > − because removing the internal path ℎ would also remove the root vertex from the tour. We choose the extension path ℎ ∈ that minimises ( ℎ ) and construct a new tour ′ = (1, . . . , ℎ− 1, ℎ , ℎ+ +1, . . . , , 1). We repeat steps for at most iterations or path ℎ ∈ such that ( ℎ ) < where:
(a) If the prize of the initial tour is less than , path extension terminates when the tour becomes prize-feasible, or terminates when is empty (the heuristic failed to find a prize-feasible tour). (b) If the prize of the initial tour is at least , path extension terminates when there does not exist a = 1 ∑︁
( ℎ )
|=1| ℎ ∈=1
(
The path extension algorithm addresses limitations of previous work in the following ways. First, on
sparse graphs, path extension can increase the prize of the tour by adding paths between non-adjacent
vertices in the tour: it is not limited by adding a single vertex between adjacent vertices of the tour. For
example, in Figure 2b, path extension recovers the optimal solution by finding an extension path with
ifve edges that replaces an internal path with three edges. Second, the unitary loss function (
To reduce the cost of a given prize-feasible tour = (1, . . . , , 1), we propose the path collapse heuristic. The intuition is to swap a sub-path of the tour for an alternative path with less cost whilst maintaining a prize-feasible tour containing the root vertex. We iterate over sub-paths of the tour (where = | ( )|) and choose the alternative path that produces the least-cost prize-feasible tour. 1. Start from vertex , then take a sub-path = (, . . . , ) of where 1 ∈ ( ) such that ( ( )) < and ( ( )) + (+1) ≥ .
to using vertices of that are not in . 2. For all neighbours ∈ () of , search for the least-cost path = (1, . . . , ) from 1 = tour ′ = (, . . . , , 2, . . . , , ) by appending ⋆ and (, ) to . 3. From ∈ (), choose the path ⋆ that minimises (()) + (, ) such that ( ( )) + ( ()) − ( ) ≥
. If (( )) + ((⋆)) + (, ) < (( )), then form a new collapsed From the collapsed tours ′ returned by step 3 in each iteration ∈ {1, . . . , }, path collapse returns the least-cost tour. Using Dijkstra’s algorithm [23] for shortest paths, the running-time of path collapse is ( · log ). Note that our path collapse algorithm contains [19] as a special case when the shortest path from to has exactly two edges. path collapse is a generalization that allows shortest paths with more than two edges. This generalization is critical in a sparse graph when a two-edge path from to may not exist. If edge ( , ) exists and is non-metric, then the generalization is important because there likely exists a least-cost path from to ∈ ( ) that does not visit edge ( , ) such that the resulting tour ′ has less cost and more prize (since ( ) + () < ()). 3.4. Suurballe’s Path Extension & Collapse (SBL-PEC)
Algorithm 1: Path extension & collapse initialised with Suurballe’s heuristic (SBL-PEC).
Input: Instance ℐ = (, , , , 1); parameter max ∈ N. Output: Tour ⋆.
2 if ( ( )) < then foreach ∈ {1, . . . , max} do path extension with termination (a); 3 ⋆ ← path collapse ; 4 for ∈ {1, . . . , max} do 5 ← path extension on ⋆ with step size with termination criteria (b); 76 if ←(p(ath))co<llap(se( ⋆;)) then ⋆ ← ;
feasible, we repeat path extension for each until ( ( )) ≥ ; then for each , we alternate path extension with path collapse. SBL-PEC has a worst-case time complexity equal to the number of times we call path extension, which is ( max2( + )).
In this section, we develop a branch & cut algorithm to find the optimal solution of sparse, non-metric instances of Pc-TSP. Our primary contribution is a new conditional cost-cover inequality based on vertexdisjoint paths (Section 4.2). For a computational study on the efectiveness of other valid inequalities for Pc-TSP such as cover and comb inequalities, we refer the reader to [14]. Our branch & cut algorithm is implemented using SCIP v8.0.3 [24, 25, 26] and linear programs are solved using CPLEX v22.1.1 [27]. 4.1. Integer Programming Formulation We formulate Pc-TSP as an integer linear program (ILP) as follows [14]. Let variable = 1 if vertex is included in the tour, or zero otherwise. Similarly, let = 1 if edge (, ) is included in the tour, or zero otherwise. We can summarise the variables as binary vectors ∈ {0, 1} and ∈ {0, 1}. Similarly the cost and prize can be represented by vectors ∈ N0 and ∈ N0 respectively. Our ILP is min s.t.
≥ 1 = 1
∑︁ ∈() ∑︁ = 2
≤ (,)∈() ∈ {0, 1}, ∈ {0, 1}.
∑︁ −
∈
∀ ∈ ()
∀ ⊂ (), 1 ∈ ()∖, ∈
(
The linear program at the root node of the branch & bound tree is defined by the objective function
(
We propose using the least-cost pair of vertex-disjoint paths between two vertices , instead of two times the cost of the shortest path. We first prove the cost of the disjoint paths are a lower bound on the shortest tour containing and : Lemma 3. In an undirected graph, the minimum cost of a tour containing and is equal to the least-cost pair of vertex-disjoint paths 1, 2 between and .
Proof. See Appendix D of the supplementary material.
By Lemma 3, ({, }) = ((1)) + ((2)) defines a lower bound on a tour containing and .
We define the disjoint-paths cost-cover (DPCC) inequality as:
+ ≤ 1
∀, ∈ (), ((1)) + ((2)) > .
(
Then we have ℱ (
Proof. To show ℱ (
Our branch & cut algorithm checks for violated cost-cover inequalities between the root vertex 1
to every other ∈ (). Before running the branch & cut algorithm, we find the least-cost pair of
vertex-disjoint paths from 1 to every ∈ () and store the costs in an array with elements. This
pre-processing step takes ( log ) for disjoint paths [22]. Note that we decided against finding the
least-cost pair of vertex-disjoint paths between every pair of vertices because it would take ( log )
time complexity and (2) space complexity. During the branch & cut algorithm, whenever a new
upper bound is discovered, if [] > then we set = 0 due to (
We evaluate our heuristics and cost-cover inequalities across multiple real-world and synthetic instances. For each instance and each algorithm, we measure the computational time in seconds (TIME) and the GAP between the upper and lower bounds. TIME is limited to four hours for each instance. For a given algorithm evaluated on a group of instances, we denote the mean GAP as GAP, the mean TIME as TIME, the number of feasible solutions as FEAS, and the number of optimal solutions as OPT. Our algorithms are implemented in C++ and Python2. The machine we use for experiments is a 2 × 10-core Xeon E5-2660 v3 at 2.6 GHz with 64GB RAM running Linux. Each run of an algorithm is allocated one core and 12GB of RAM using the slurm scheduler [28].
London Air Quality (LAQ) We generate instances of the LAQ dataset by mapping air pollution forecasts from a machine learning model onto the London road network. The air quality model of London [11] is a non-stationary mixture of Gaussian Processes that predicts air pollution (nitrogen dioxide) from data such as sensors, road trafic and weather. The model output consists of forecasts for each cell of a hexagonal grid which overlays the road network (see Figure 1). Every road has a length (in meters). The cost of running along a road is the mean pollution of the grid cells intersecting the road multiplied by the length of the road. The goal is to minimise air pollution exposure of a tour such that the total length of the tour is at least the quota and the tour starts and ends at the root vertex.
The LAQ dataset consists of four graphs3 named laqbb, laqid, laqkx and laqws which are each created by only keeping vertices within 3000m of the root vertex. The root vertex of each graph is given respectively by the following four locations in London: Big Ben (bb), Isle of Dogs (id), King’s Cross (kx), and Wembley Stadium (ws). The prize function of vertices is generated by splitting each edge (, ) in the graph into two edges (, ), (, ) and assigning the length of edge (, ) to the prize of a newly created vertex . The prize of and is zero. The cost of (, ) is the same as (, ) but the cost of (, ) is set to zero. The metric surplus (, ) (see Definition 4) of instances in the LAQ dataset is approximately 0.9. For each of the four graphs, we run our algorithms on five diferent quotas (1000m, 2000m, 3000m, 4000m, or 5000m), giving us 20 diferent instances for the London air quality dataset. 2Code available at https://github.com/PatrickOHara/pctsp. Datasets available upon request. 3We constructed smaller graphs because running our algorithms on the entire London road network (which has hundreds of thousands of vertices and edges) was too computationally expensive.
TSPLIB A well-known benchmark dataset used in multiple papers [29, 14, 16], TSPLIB [21] is a collection of complete graphs. We chose nine graphs with a range of sizes from the original TSPLIB dataset: eil514, st70, rat195, tsp225, a280, pr439, rat575, gr666, pr1002. We construct sparse graphs with a metric surplus of zero (meaning every edge is non-metric). Each vertex is labelled from 1, . . . , and is assigned an x and y co-ordinate. The root vertex is labelled 1 = 1. Let the Euclidean distance between the co-ordinates of vertices and be || − ||2. The prize () of vertex is defined by three diferent generations [14, 16]: (i) () = 1; (ii) () = 1+(7141+73) mod 100; and (iii) () = 1+⌊ 9 9 ||1− ||2⌋ where = max∈ () ||1 − ||2. We set = · ( ()) where ∈ {0.05, 0.10, 0.25, 0.50, 0.75}. To make the graphs sparse, we remove edges from TSPLIB instances with independent and uniform probability until the number of edges is equal to where ∈ {5, 10, 15, 20, 25}.
The cost function is called MST with (, ) = 0 and is defined as follows. First, assign all edges cost || − ||2. Next, find the minimum spanning tree of the sparse graph . Now, find the shortest path from vertex to using only edges in ( ). Finally, assign costs such that edges in are metric and edges not in are non-metric: (, ) = {︃ ⌈|| − ||2⌉ ⌈|| − ||2⌉ + (( )) ∀(, ) ∈ ( ) ∀(, ) ∈ ()∖( ) In summary, there are 675 instances in the modified TSPLIB dataset: five levels of sparsity, three prize generating functions, nine distinct graphs, and five values of . 5.1. Empirical Heuristic Results In this section, we compare SBL-PEC against a baseline (BFS-EC) from the literature. The BFS-EC baseline initialises the Extension & Collapse (EC) [19] with the first cycle detected by a Breadth First Search (BFS). We also run Suurballe’s heuristic (SBL) as a stand alone heuristic. When calculating the GAP, the upper bound (UB) is the total cost of the heuristic solution. The lower bound (LB) is the cost of the largest lower bound found by running our branch & cut algorithm in Section 4 with disjoint-paths cost-cover (DPCC) cuts for a maximum of four hours. On instances where the optimal solution is found within four hours, LB will be the cost of the optimal solution (denoted with a ⋆ in Table 1 and Table 2). For a given instance, each heuristic is compared against the same LB when calculating the GAP. From Table 1 and Table 2, we conclude the following: • SBL finds low-cost initial tours. On the LAQ dataset, the GAP is equal for SBL and SBL-PEC on every instance, implying PEC does not improve the SBL tour because SBL finds a solution that is optimal or close-to-optimal, so little improvement is possible. On TSPLIB, PEC is needed to make the SBL tour prize-feasible. • BFS-EC [19] cannot suficiently increase the prize. On both LAQ and TSPLIB datasets, BFS-EC ifnds less feasible tours than SBL-PEC. On TSPLIB when is sparse ( = 5), BFS-EC finds 8/135 feasible tours compared to 123/135 for SBL-PEC. • SBL-PEC is the best heuristic on TSPLIB. In addition to finding the most feasible tours, when ≥ 10, the GAP of BFS-EC is consistently four times more than the GAP of SBL-PEC.
To conclude our heuristic analysis, SBL is efective as a standalone heuristic on the LAQ dataset, whilst SBL-PEC outperforms all other algorithms on the TSPLIB dataset across varying levels of sparsity. 4Code “eil51” means there are 51 vertices in the original TSPLIB instance. GAP due to the heuristic finding zero feasible solutions to the four instances. GAP is marked by ⋆ if LB is the optimal solution to all four instances found by branch & cut; else GAP is unmarked such that LB is the largest lower bound and the GAP is an overestimate. row corresponds to 135 instances. GAP is calculated using the largest lower bound (LB), and so the GAP is an overestimate for each entry.
BFS-EC
SBL
SBL-PEC 5 10 15 20 25
GAP 5.2. Cost-cover Inequalities To evaluate our disjoint-paths cost-cover (DPCC) cuts, we run our branch & cut algorithm from Section 4 with DPCC against shortest-path cost-cover (SPCC) cuts. To find an upper bound , we run SBL-PEC. In addition to TIME and GAP, we record PRE-CUTS: the number of cost-cover cuts added to the first linear program of the root node of the branch & cut tree before the solver is started due to the initial upper bound . We found PRE-CUTS to be a more informative metric than total number of cost-cover cuts because the latter can be afected by factors such as the number of times an upper bound is found during the solving process. From Table 3 and Table 4, we conclude: • DPCC adds more PRE-CUTS than SPCC. Across all quotas on LAQ dataset, DPCC adds at least 300 more PRE-CUTS than SPCC. On TSPLIB for = 0.05 and = 0.10 respectively, DPCC adds 61 and 23 more PRE-CUTS than SPCC, resulting in DPCC finding 5 more and 3 more optimal solutions than SPCC respectively. This is empirical evidence of Proposition 4. • On LAQ, DPCC finds the optimal solution three times faster than SPCC when ≤ 4000. Furthermore, the GAP of DPCC is three times less than SPCC when = 5000. Both DPCC and SPCC find 17 out of 20 optimal solutions. • Few PRE-CUTS are added when
= 0.25, 0.50, 0.75. The result is less than 90 second TIME diference between DPCC and SPCC for
= 0.25, 0.50, 0.75. Few PRE-CUTS are added because larger
means collecting more prize, which will generally incur a greater cost, thus increasing
the initial upper bound ⋆ at the root of the branch & bound tree. For all least-cost vertex-disjoint
paths 1, 2 from 1 to ∈ (), if ((1)) + ((2)) < ⋆ , then zero DPCC cuts will be
added because the condition in (
Disjoint-paths cost-cover cuts
To summarise, we have designed algorithms for the Prize-collecting Travelling Salesperson Problem on sparse graphs with non-metric cost functions. Suurballe’s heuristic found optimal or close-to-optimal solutions on the London Air Quality dataset and proved to be a good starting solution for PEC on the TSPLIB dataset. Our combined SBL-PEC heuristic found a solution with less cost than Extension & Collapse [19] on every instance across both datasets. We derived a disjoint-paths cost-cover (DPCC) cut that tightens the lower bound, then proved the size of the set of solutions defined by the DPCC inequality is at most the size of the set of solutions defined by the SPCC inequality. On the London Air Quality dataset, our DPCC branch & cut algorithm finds optimal solutions three times faster than SPCC for quotas 1km to 4km, whilst the GAP is three times less when the quota is 5km. On the TSPLIB dataset with non-metric costs, DPCC solves more instances to optimality than SPCC.
Our methods can be applied to other family members of TSPs with Profits [ 5, 16] and other related routing problems [30, 31]. One example is the Orienteering Problem (OP): maximise the total prize of a tour starting and ending at the root vertex such that the total cost is at most an upper bound ∈ N. If the least cost of two vertex-disjoint paths between vertices , is greater than , then and cannot both be in a feasible solution to OP. Therefore, the DPCC inequality for Pc-TSP can be re-written as a valid inequality for OP which is stronger than the SPCC inequality (by Proposition 4).
Future work on the sparse, non-metric Prize-collecting Travelling Salesperson Problem could exploit the rich problem structure ofered by our motivating example of running routes that minimise air pollution: dynamic algorithms that optimise a route as air pollution changes over time; multi-objective algorithms that optimise over multiple pollutants; and stochastic optimisation algorithms that consider the uncertainty in predictions from the air quality model.
PO and TD acknowledge support from a UKRI Turing AI Acceleration Fellowship [EP/V02678X/1] and a Turing Impact Award from the Alan Turing Institute. PO also acknowledges support from the Department of Computer Science Studentship of the University of Warwick. MSR acknowledges support from UKRI EPSRC Research Grant [EP/V044621/1]. Batch Computing facilities were provided by the Department of Computer Science of the University of Warwick. The authors would like to thank Oliver Hamelijnck for providing air quality forecasts of London for the experiments. For the purpose of open access, the authors have applied a Creative Commons Attribution (CC-BY) license to any Author Accepted Manuscript version arising from this submission
As is shown in Table 5, the literature on Pc-TSP assumes the input graph is complete and/or the cost function is metric. Given a sparse graph with a non-metric cost function, one may ask why we cannot simply construct a complete graph ′ with metric costs, then run an algorithm from the literature on ′? We give two such graph constructions in this section and explain why they do not work. Least-cost path construction The first construction is as follows: for every pair of vertices , in , ifnd the least-cost path from to in , then set the cost of a new edge from to in ′ equal to the cost of . The problem with such a construction is that a feasible solution to the constructed instance on ′ is not guaranteed to be a simple cycle in the original input graph . Moreover, this construction may not be desirable when is sparse because the number of edges in ′ will be far greater than , resulting in more variables to optimise when calling algorithms such as linear programs. Dummy edge construction The second construction takes as input a sparse graph and constructs a complete graph ′ as follows. Add a vertices in to ′ and add all edges in to ′ with the same cost. Now, for all pairs of vertices , in such that (, ) is not an edge in , we add a dummy edge (, ) to ′ and set the cost of (, ) to be some very large constant (e.g. we could take = ∑︀(,)∈() (, ). The constructed graph ′ is clearly a complete graph and the optimal solution to any instance does not contain dummy edges. However, the major problem with this construction is that naively running a heuristic from the literature on ′ may return a solution that contains a dummy edge, that is, the returned solution is not guaranteed to be feasible for the original instance. Moreover, the cost function is still non-metric, which naturally rules out any algorithm from the literature which requires a metric cost function. Finally, the dummy edge construction also increases the computational complexity of algorithms from the literature because the number of edges has been increased from () to (2).
For completeness, we give proofs of Lemma 1 and a proof of correctness for the preprocessing algorithm. B.1
Number of metric edges Lemma 1. Let be a connected, undirected graph and : () → N0 be a cost function on the edges. The number of metric edges in () is at least − 1.
Proof. Let ⊆ () be the set of metric edges in . Let the sub-graph be defined by vertices ( ) = () and edges ( ) = . To show | | ≥ − 1, it is suficient to show that is connected. By contradiction, suppose is not connected and let 1, . . . , be the connected components of . Since is connected, there exists a least-cost path = (, . . . , , , . . . , ) in from ∈ () to ∈ ( ) such that ̸= visits an edge (, ) where ∈ (), ∈ () and ̸= . Note that every sub-path of is itself a least-cost path. Then edge (, ) defines a least-cost path from to , so (, ) is a metric edge and should have been in . This implies every two adjacent edges in are in the same connected component of , so all , ∈ ( ) are in the same connected component and is connected.
B.2
Biconnected component pre-processing algorithm A biconnected component of is a maximal sub-graph such that the removal of a single vertex (and all edges incident on that vertex) does not disconnect the sub-graph. The biconnected components of an undirected graph can be found in time ( + ) [33]. Let = {1, . . . , } be the set of biconnected components of . Our pre-processing algorithm removes a vertex from the input graph if there does not exist a ∈ {1, . . . , } such that and 1 are both in . To see why our pre-processing algorithm is correct, note that every vertex in a feasible tour must be biconnected to 1 (otherwise there would exist some vertex in the tour which must be visited more than once). A trivial example of a vertex not in the same biconnected component as 1 is a leaf vertex with degree one.
We give a complete proof of correctness for our pre-processing algorithm. Given a subset of vertices ⊆ (), the induced sub-graph [] contains all vertices in and contains all edges in () that have both endpoints in . Formally, a biconnected component of is a maximal sub-graph such that the removal of a single vertex (and all edges incident on that vertex) does not disconnect the subgraph. We define 1, . . . , ⊆ () to be vertex sets such that [1], . . . , [] are the biconnected components of .
Lemma 5. Let [1], [2] be any two maximal biconnected components of . Then |1 ∩ 2| ≤ 1. Proof. Suppose that |1 ∩ 2| > 1 and let ′ = 1 ∪ 2. Our claim is that [′] is a biconnected component. To prove this claim, take two vertices , ∈ ′. If , ∈ 1 (or if , ∈ 2), then and are already in the same biconnected component. If ∈ 1∖(1 ∩ 2) and ∈ 2∖(1 ∩ 2), then remove a vertex 1 ∈ 1 ∩ 2. This removal does not disconnect the sub-graph [′] because there exists a path from to via some distinct 2 ∈ 1 ∩ 2 where 2 ̸= 1 (since |1 ∩ 2| > 1). [′] is therefore a larger biconnected than [1] and [2], so [1], [2] are not maximal biconnected component components.
Lemma 6. Assume is connected. Let [1], [2] be any two maximal biconnected components of such that 1 ̸= 2. Let tour be a feasible solution to an instance of Pc-TSP. If visits at least two vertices excluding 1 in 1, i.e. |( ( ) ∩ 1)∖{1}| ≥ 2, then does not visit any vertices in 2∖(1 ∩ 2). Proof. From Lemma 5, we have two cases: (i) 1 ∩ 2 contains exactly one vertex ; or (ii) 1 ∩ 2 = ∅.
, and once on the way back) which is contradiction to the definition of a tour. For case (ii), there exists exactly one biconnected component5 [3] such that 3 ̸= 1 ̸= 2 and 1 ∩ 3 ̸= ∅. Any tour that visits a vertex in 2 must also visit a vertex in ∈ 3∖(1 ∩ 3). By the same logic as case (i), no tour can visit , therefore no tour can visit 2.
Applying Lemma 6 to every biconnected component that does not contain the root leads to our main pre-processing result: Corollary 7. Let = ⋃︀{|1 ∈ , ∈ {1, . . . , }} be the set of vertices in the same biconnected component as the root vertex. There does not exist a feasible solution that visits a vertex in ()∖. Vertices in ()∖ (and their adjacent edges) can safely be removed from the input graph without removing any feasible solutions. 5We can construct an undirected graph by representing each biconnected components as a vertex in . Note will be acyclic. If is connected, then is a connected tree.
Proposition 2. Assume ̸= . Let be any undirected graph. No polynomial-time algorithm is guaranteed to find a feasible solution (if one exists) for every instance of Pc-TSP.
Proof. By contradiction, assume is guaranteed to find a feasible solution for every instance of Pc-TSP in polynomial-time. Let ℐ = (, , , , 1) be an instance such that = ( ()). The only feasible solutions to ℐ are Hamiltonian cycles of . Then is guaranteed to find a Hamiltonian cycle in polynomial-time for any simple, undirected graph . Since finding a Hamiltonian cycle -hard, this implies = , a contradiction to our assumption.
Lemma 3. In an undirected graph, the minimum cost of a tour containing and is equal to the least-cost pair of vertex-disjoint paths 1, 2 between and .
((2′)) < ((1)) + ((2)), then 1, 2 are not the least-cost vertex-disjoint paths between and . If ((1′)) + ((2′)) > ((1)) + ((2)), then there exists a tour ′ containing and with less cost than , because we can construct ′ by reversing the order of 2 and appending it to 1. So 1′, 2′ are least-cost vertex-disjoint paths and the minimum cost of the tour is (( )) = ((1′)) + ((2′)) = ((1)) + ((2)).
E.1
Separation Algorithms In a branch & cut algorithm, a separation algorithm identifies violated inequalities. We give polynomialtime separation algorithms for the sub-tour elimination constraints (SECs).
E.1.1 Sub-tour Elimination Constraints Definition 5. The support graph ⋆ of the solution (⋆, ⋆) to linear program is defined by the vertex set (⋆) = { ∈ () : ⋆ > 0} and edge set (⋆) = {(, ) ∈ () : ⋆ > 0}.
Constraints (
E.2
Variable Branching When a linear program at node in the branch & bound tree is solved, we may choose to branch on a variable that is fractional in . Branching on a variable means creating two new child nodes +, − of with linear programs + and − respectively. + is defined by inheriting all variables and constraints in and then rounding variable up to the nearest integer ( = 1). − is defined similarly by rounding down ( = 0). Choosing which fractional variable to branch on has been the subject of extensive research [35]. In their branch & cut algorithm for Pc-TSP, Bérubé et al. [14] branch on the most fractional variable. However, more advanced branching strategies can Run SBL-PEC
heuristic Create LP at root
node Add cost-cover cuts w.r.t SBL-PEC tour Add cost-cover cuts
Node selection
Branch
Yes Is solution the smallest upper bound?
No
Solve LP
Add SEC cuts Is solution integer and feasible? Yes
No
No Tailing off?
Yes | ()| |()| ( ()) | ()| |()| ( ()) ( ()) (, ) () ( ()) laqbb laqid laqkx laqws yield smaller branch & bound trees, reducing the total computational time for solving a problem to optimality. Our branch & cut algorithm uses strong branching [29] at the top node of the branch & bound tree, then uses reliability branching [35] on all subsequent nodes in the tree.
We make one final addition to our branch & cut algorithm to prevent the phenomena of tailing of . This is where adding cuts to consecutive relaxed linear programs from the same node does little to improve the lower bound. To test if a node in the branch & bound tree is tailing of, we check if GAP − GAP− ≤ where GAP is the GAP between the lower bound and upper bound after iterations of adding cuts, ∈ N is a parameter controlling the maximum number of iterations cuts can be added to a linear program without showing improvement, and ∈ R is the LP gap improvement threshold. If we find a node is tailing of, we branch on a variable, instead of waiting for more cuts to be added. After some experimentation (see Section J), we set = 5 and = 0.001. To summarise, if after
Statistics for the TSPLIB dataset aggregated by the sparsity level and the cost function (EUC or MST). The original input graph is and the pre-processed graph is . The column AVG (︁ ( ()) )︁ denotes the average total prize of as a ratio of . The column AVG(()) is an average of () as defined ( ()) 5 10 15 20 25
AVG(()) ifve iterations of adding cuts to a linear program the GAP has improved by at most 0.001, we branch on a variable instead of adding more cuts. Figure 3 shows a visualisation of our branch & cut algorithm.
Before outlining the complementary experiments, we give more details about the LAQ and TSPLIB datasets. Moreover, for the TSPLIB dataset, we introduce a metric cost function called EUC. It is defined simply as the Euclidean distance between the coordinates of two vertices , ∈ () in the TSPLIB dataset: (, ) = || − ||2. total prize of the graph:
Table 6 shows a summary of instances in the LAQ dataset and Table 7 shows a summary of instances in the TSPLIB dataset. The table includes a graph property : → [0, 1] which is defined to be the largest prize of a pair of least-cost vertex-disjoint paths 1, 2 from 1 to ∈ () as a ratio of the () =
1
( ()) ∈ ()
max {( (1)) + ( (2)) − ()}
(
Pre-processing The biconnected component pre-processing algorithm described in Section B.2 removes more vertices (and more prize) from the LAQ input graph than on the TSPLIB input graph because the LAQ graphs are more sparse than TSPLIB. From Table 7, we see that on TSPLIB the average prize removed from the graph during pre-processing increases as the graph becomes more sparse ( decreases). Even when = 5 on TSPLIB, less than 10% of the prize is removed from the input graph during pre-processing. In contrast on the LAQ dataset in Table 6, our pre-processing algorithm removes more than 25% of the prize on laqid and laqws, and removes 15.8% and 18.1% on laqbb and laqkx. To summarise, our pre-processing algorithm is efective at reducing the input size when the graph is sparse.
Section G shows heuristics results in the same manor as the TSPLIB results of Table 2 but with the extra cost function EUC and with two addtional heuristics called BFS-PEC and SBL-EC. After generating an initial tour with BFS, the BFS-PEC heuristic increases the prize with the path extension heuristic, then decreases the cost with the path collapse heuristic. After generating an initial tour with SBL, SBL-EC increases the prize with Extension, then decreasing the cost with Collapse [19].
Cost The GAP and FEAS for five heuristics on the TSPLIB dataset across both the EUC and MST cost functions and across diferent sparsity levels . Each row corresponds to 135 instances. GAP is calculated using the largest lower bound (LB) and so the GAP is an overestimate for each entry. For a given , each row reports the number of feasible solutions (FEAS) found by a heuristic on the TSPLIB dataset across both the EUC and MST cost functions. The largest possible value of FEAS is 270. sparse ( = 5) and the quota is large ( = 0.75): BFS-PEC finds 246 out of 270 feasible solutions and SBL-PEC finds 248 out of 270 across both cost functions. The GAP of SBL-PEC is smaller than BFS-PEC across every for both cost functions, but the diference in the GAP between the two algorithms is more noticeable on the MST cost function. When the cost function is non-metric (MST), the diference in the GAP between BFS-PEC and SBL-PEC is greater than 0.33 for all ; and when the cost function is metric (EUC), the diference in the
GAP between BFS-PEC and SBL-PEC is less than 0.11 for all . This suggests initialising PEC with SBL is particularly efective on non-metric cost functions .
The GAP of SBL-EC is greater than BFS-PEC and SBL-PEC across both cost functions and all values of . Moreover, SBL-EC finds less feasible solutions than BFS-PEC and SBL-PEC. Compared to BFS-EC, SBL-EC finds more feasible solutions, suggesting it is better to initialise EC with SBL than BFS: this is the same conclusion we came to for initialising PEC. The GAP of SBL-EC is generally greater than BFS-EC on the EUC cost function, but less than BFS-EC on MST cost function (however these figures are not directly comparable because SBL-EC finds more feasible solutions).
Whilst SBL is highly efective on the LAQ dataset, Table 9 shows SBL is less likely to find a feasible solution as increases on the TSBLIB dataset. This is unsurprising because a pair of least-cost vertexdisjoint paths between 1 and ∈ () is unlikely to collect a lot of prize, thus if is large then SBL will not collect enough prize to meet the quota. More specifically, if () > then SBL will not find a feasible solution. For example, Table 7 shows that AVG(()) = 0.062 on the EUC cost function when = 5, so if
= 0.75 then SBL will not find a feasible solution. One reason SBL is highly efective on the LAQ dataset is that is small: for example, a quota of 5000 on the laqbb graph gives ≈ is less than () = 0.021. To conclude our analysis of heuristics, SBL is efective as a standalone 0.01 which heuristic on the LAQ dataset, whilst SBL-PEC outperforms all other algorithms on the TSPLIB dataset across two cost functions and varying levels of sparsity.
SBL
FEAS 18 15 12 11 8 46 48 51 51 54 GAP Evaluation of our branch & cut algorithm using no cost-cover (NoCC) inequalities on the London air quality dataset for five diferent quotas. There are four instances for each quota. Evaluation of our branch & cut algorithm using no cost-cover (NoCC) inequalities on the TSPLIB dataset for five diferent values of and two diferent cost functions. Each row corresponds to 135 instances. 1000 2000 3000 4000 5000 Cost EUC MST 0.05 Disjoint-paths cost-cover cuts
Shortest-path cost-cover cuts 0.05 0.10 0.25 0.50 0.75 57 9 0 0 0 Evaluation of our branch & cut algorithm using disjoint-paths vs shortest-path cost-cover inequalities on the TSPLIB dataset with EUC cost function for five diferent values of . Each row corresponds to
In this section, we conduct two additional experiments. Firstly, we ask: does running a branch & cut algorithm with cost-cover inequalities actually make a diferent? We find an afirmative answer by running our branch & cut algorithm with no cost-cover (NoCC) inequalities and compare it against DPCC and SCPCC. Second, we analyse DPCC and SPCC on a metric cost function (EUC). H.1
No cost cover inequalities DPCC and SPCC from Table 3. NoCC finds just 7 out of 20 optimal solutions, whereas DPCC and SPCC both find 17 out of 20. We conclude that adding cost cover inequalities is highly advantageous on the 50 8 0 0 0
GAP LAQ dataset.
On TSPLIB with MST costs when = 0.05 and = 0.10, NoCC adds zero cost-cover cuts, so DPCC ifnds 9 more and 5 more optimal solutions than NoCC for = 0.05 and = 0.10 respectively. The TIME of DPCC is less than NoCC when = 0.05 and = 0.10: DPCC terminates 1,530 and 610 seconds faster respectively than NoCC.
both DPCC and SPCC. Indeed when DPCC and SPCC add zero cost-cover cuts in total, then DPCC, SPCC, and NoCC are nearly equivalent branch & cut algorithms (minus the added computational time needed to run the cost-cover separation algorithm). This results in less than 90 second TIME diference between DPCC, SPCC, and NoCC for all ∈ {0.25, 0.50, 0.75}. Small variations in the GAP and OPT further support that there is little diference on MST costs between DPCC, SPCC, and NoCC when ∈ {0.25, 0.50, 0.75}: SPCC has the smallest GAP by 0.004 when = 0.25; DPCC has the smallest GAP by 0.032 when = 0.50; and NoCC has the smallest GAP by 0.003 when = 0.75. H.2
Metric costs The EUC cost function on the TSPLIB dataset, as defined in Section F, is a metric cost function (see Definition 3). The cost-cover results for EUC on TSPLIB are shown in Table 12. For each , less PRE-CUTS are added by DPCC on EUC compared to when the cost function is MST. For example, when = 0.05, the number of PRE-CUTS added by DPCC is 56.7 on EUC compared to 192 on MST. Moreover, for all values of , the diference in the number of PRE-CUTS between DPCC and SPCC on the EUC cost function is smaller than on the diference MST cost function. As a result, conclude that for the EUC cost function, small variations across in the TIME, GAP and OPT show there is little diference between DPCC, SPCC, and NoCC.
Our results show a discrepancy between the LAQ and TSPLIB datasets. For completeness, we run the same experiments as Section 5 on the LAQ dataset for both our heuristics and our branch & cut algorithm, but instead of setting the quota to be ∈ {1000, 2000, 3000, 4000, 5000}, we set the quota = · ( ()) in the same manor as our experiments on TSPLIB with ∈ {0.05, 0.10, 0.25, 0.50, 0.75}. The experimental results for heuristics are summarised in Table 13 and for diferent cost-cover cuts in Table 14.
First, as we noted in Section F.1, our biconnected component pre-processing algorithm described in Section 2 removes more vertices (and more prize) from the LAQ input graph than on the TSPLIB input graph because the LAQ graphs are more sparse. From Table 7, we see that on TSPLIB the average prize removed from the graph during pre-processing is less than 10% across all sparsity levels . Contrast this to the LAQ dataset in Table 6, where on two LAQ instances (laqid and laqws), our pre-processing algorithm removes more than 25% of the prize in the original input graph. This means when = 0.75 for laqid and laqws, the total prize of the pre-processed graph is not greater than the quota, which trivially shows the original instance does not have a feasible solution. On laqbb and laqkx, the preprocessing algorithm removes 15.8% and 18.1% of the total prize of the original graph. Whilst in theory the two graphs contains suficient prize for a quota set with = 0.75, the bottom row of Table 14 shows our branch & cut algorithm quickly determines there are no feasible solutions to the two instances. Moreover, when = 0.50, neither our heuristics nor our branch & cut algorithm found a feasible solution to any of the four instances. The branch & cut algorithm was able to obtain a lower bound, but not able to prove infeasibility within the four hour time limit, and it remains open whether there exists a feasible solution to these four instances when = 0.50.
feasible solutions to these LAQ instances. Contrast this to TSPLIB (Table 9) where BFS-EC finds 204, 194, 187 feasible solutions for = 0.05, 0.10, 0.25 respectively. Similarly SBL finds 181, 107, 26 feasible solutions on TSPLIB for = 0.05, 0.10, 0.25 respectively. As noted in Section 5.1, EC on LAQ cannot
A comparison of heuristic performance on the LAQ dataset for each We measure the GAP and FEAS across all four instances (laqbb, laqid, laqkx, laqws). “nan” means “not a number” where we could not calculate a GAP due to the heuristic finding zero feasible solutions to the ∈ {0.05, 0.10, 0.25, 0.50, 0.75}. Evaluation of our branch & cut algorithm with DPCC and SPCC on the London air quality dataset for ∈ {0.05, 0.10, 0.25, 0.50, 0.75}. There are four instances for each quota. “nan” means “not a number” and represents an upper bound (UB) that could not be calculated for all four instances for a given (the corresponding GAP also cannot be calculated). “inf” means “infeasible” and represents instances for which no feasible solution exists for all four instances.
Disjoint-paths cost-cover cuts
Shortest-path cost-cover cuts 0.05 0.10 increase the prize of the initial tour generated by BFS due to the sparsity of the graph, resulting in for
∈ {0.05, 0.10, 0.25}, notice that for all instances in the LAQ experiment where ≥
zero feasible solutions to ∈ {0.05, 0.10, 0.25}. To explain why SBL does not find feasible solutions
function () (see (
st70, eil76, rat195) with ∈ {10, 20} and ∈ {0.25, 0.75}.
In this section, we justify our Strong at Tree Top (STT) branching strategy from Section E.2 against Relative Pseudo Cost (RPC) branching with empirical experiments across both datasets. We also include an analysis of how the parameters for preventing tailing of were chosen. To isolate the efects of the branching strategy, we do not add any cost-cover cuts and SCIP features are turned of. Our brief experiments with most fractional branching for Pc-TSP as proposed by [14] yielded very large branch & bound trees at great computational cost and are excluded from this analysis. For the STT strategy, we set a depth limit of Δ ∈ {1, 5, 10}. RPC has no depth limit (marked as N.A.). For both branching strategies, we set the tailing of threshold to be ∈ {0.001, 0.01} and the maximum number of iterations to be ∈ {5, 10, ∞}. This corresponds to 24 diferent parameter configurations. We run each parameter configuration on a subset of both datasets. On LAQ, we test each graph (laqbb, laqid, laqkx, laqws) for quotas ∈ {1000, 2000, 3000}. For the TSPLIB dataset, we restrict the instances to four graphs (att48, Table 15 and Table 16 summarise the results for each parameter configuration for the LAQ and 1 5
STT
STT 10
STT ∞ 5 10 ∞ 5 10
TIME Branching strategy and tailing of results on the LAQ dataset. The bold row in both tables highlights the parameter configuration for STT as chosen for our branch & cut algorithm in Section E.2.
OPT
FEAS
NODES TSPLIB datasets respectively. The bold row in both tables highlights the parameter configuration for STT where Δ = 1, = 0.001 and
= 5 as chosen for our branch & cut algorithm in Section E.2.
Across both datasets, the tables show the GAP of STT is less than RPC. On TSPLIB, STT is strongest when Δ ∈ {1, 5}. On LAQ, the smallest GAP is 0.04 when STT uses Δ = 1, = 0.001 and = 5. Since STT with Δ = 1, = 0.001 and = 5 also performs well on TSPLIB, we chose this as our branching and tailing of parameter configuration. STT with
Δ = 5, = 0.001 and = 10 also has a small GAP of 0.05 on LAQ, but the NODES, SEC and TIME on TSPLIB were larger. Branching strategy and tailing of results on the TSPLIB dataset. The bold row in both tables highlights the parameter configuration for STT as chosen for our branch & cut algorithm in Section E.2. Δ
OPT
FEAS
NODES ∞ ∞ ∞ ∞ ∞ ∞
TIME
GAP 0.07 41 41 41 40 41 41 42 43 43 42 42 43 43 43 43 43 42 43 42 42 42 42 48 48 48 48 48 48 47 48 48 47 48 48 48 48 48 48 48 48 48 48 48 48 48 2716.92
SEC 56.13