© The Author(s), under exclusive license to APress Media, LLC, part of Springer Nature 2022
R. WienerGeneric Data Structures and Algorithms in Gohttps://doi.org/10.1007/978-1-4842-8191-8_18

18. Branch-and-Bound Solution to TSP

Richard Wiener1  
(1)
Colorado Springs, CO, USA
 

The previous chapter introduced the famed Travelling Salesperson Problem (TSP). A brute-force solution was presented. Like all exact solutions to this problem, it is computationally intractable. A third-party package was presented along with code for graphically displaying a TSP tour.

This chapter presents another exact solution to TSP using a powerful technique, branch and bound. It too is computationally intractable.

In the next section, we introduce the technique of branch and bound and show how it can be applied to TSP.

18.1 Branch and Bound for TSP

Much of this chapter is based on a paper written by this author and published in the Journal of Object Technology in 2003. The paper is “Branch and Bound Implementation for the Traveling Salesperson Problem” (Richard Wiener, Journal of Object Technology, Vol 2. No. 3, May–June 2003).

We are given a graph that contains distances connecting all cities (each city is connected to every other city with an edge representing the distance between the two cities). The nodes of the graph are the cities, numbered 0, …, n - 1. A tour is a sequence of cities that starts at city 0, visits each of the other cities exactly once, and returns to the starting city 0.

In any tour, the value of an edge when leaving a city must be equal or greater than the value of the shortest edge leaving the city.

This forms the basis for a branch-and-bound solution to TSP.

An Example

Consider a TSP with the following distance matrix (cost matrix):

  0  14    4   11   20

14    0    7     8      7

   4     7    0     7   16

11    8    7     0     2

20    7  16     2     0

We build a solution tree as follows:

At level 0, the root node represents a partial tour [0].

At level 1, nodes representing the partial tours [0, 1], [0, 2], [0, 3], …, [0, n - 1] are generated.

At level 2, nodes representing the partial tours [0, 1, 2], [0, 1, 3], [0, 1, 4], … are generated.

This pattern continues until at the lowest level, we have every permutation for all tours.

Computation of Lower Bound

For the root node of the preceding graph, with partial tour [0], the lower bound on the costs of leaving the five vertices is

City 0: minimum (14, 4, 11, 20) = 4.

City 1: minimum (14, 7, 8, 7) = 7.

City 2: minimum (4, 7, 7, 16) = 4.

City 3: minimum (11, 8, 7, 2) = 2.

City 4: minimum (20, 7, 16, 2) = 2.

Therefore, the lower bound for the TSP solution based on the partial tour [0] is the sum of these values, which is 19.

Let us compute the lower bound for a partial tour [0, 2, 3].

City 0: 4 (since the tour contains 0 -> 2)

City 1: 7 (cannot touch node already on tour)

City 2: 7 (since the tour contains 2 -> 3)

City 3: 11 (since the tour contains 3 -> 0)

City 4: 7 (cannot touch node already on tour)

Therefore, the lower bound for the partial tour [0, 2, 3] is the sum, which equals 36.

The computational cost of computing the lower bound for a partial tour is low.

At any level in the tree containing partial tours, the nodes can be ranked by their computed lower bounds. We can use a priority queue to hold the tree structure.

Branch-and-Bound Algorithm

  • Set an initial value for the best tour cost.

  • Initialize a priority queue (PQ).

  • Generate the first node with partial tour [0] and compute its lower bound.

  • Insert this node into PQ.

  • While the PQ is not empty, remove the first node from the PQ and assign it to parent.

  • If its lower bound < best tour cost, set its level to the level of parent node + 1.

  • If this level is N – 1, where N is the number of cities, add starting city 0 to the end of the partial tour and compute the cost of the full tour.

  • If this cost of full tour < best tour cost, update the best tour cost and save the best tour.

  • If the level of the parent node + 1 is not equal to N – 1,

  • For all i such that 1 <= i < N and i is not in the partial tour of the parent,

  • Copy the partial tour from parent to new node and add i to the end of this partial tour.

  • Compute the lower bound for this new node.

  • If this lower bound is less than the best tour cost, insert this new node into the priority queue; otherwise, prune this node.

The Priority Queue

Before a node is inserted into the PQ, it is screened to determine whether its lower bound is less than the currently known best tour. This helps to keep the number of nodes in the PQ to a manageable level.

What priority rules must the queue enforce?

Nodes at a deeper level (higher level number) have priority over nodes at a shallower level in the PQ. This assures that the tree grows downward and that leaf nodes representing complete tours are generated as quickly as possible. In comparing two nodes at the same level, priority is given to the node with the smallest lower bound. In the event of a tie (two nodes with equal lower bound), the sum of the cities in the partial tour is computed. The node with the smaller sum is given a higher priority than the node with the larger sum (a tie cannot occur). The rules just stated disallow two distinct nodes from having an equal priority.

We walk through a portion of the five-city example presented earlier to see how the priority queue is built.

A Walk-Through Part of the Five-City Example Presented Earlier

The initial cost is computed by finding the cost of the tour, [0, 1, …, n – 1, 0], which is 50. Since the lower bound (LB) of the root node was shown earlier to be 19, we push the partial tour [0] onto the PQ. We remove tour[0] from the PQ and generate nodes at level 1. All but one of these nodes have LB < 50, so we push them onto the PQ. The top of the PQ is [0, 2] with LB = 19. Next comes [0, 1] with LB = 39, and third comes [0, 3] with LB= 43. We continue to generate nodes as specified in the algorithm and as shown in Figure 18-1.

A flow diagram depicts the main dark shaded rectangle 0 within closed brackets 19 simplifying to four other rectangles named as 0 and 1 within closed brackets, 39 as 0, 1, 39; 0, 2, 19; 0, 2, 1, 29; 0, 2, 1, 3, 30; 0, 2, 1, 3, 4, 41; 0, 2, 1, 4, 38; 0, 2, 3, 36; 0, 2, 4, 56; 0, 3, 43; 0, 4, 61.

Figure 18-1

Part of solution tree

The full tour [0, 2, 1, 3, 4] is the first to be generated. Since its cost is less than the best so far of 50, we assign the best tour to be [0, 2, 1, 3, 4] and its cost 41.

The front of the PQ contains the node [0, 2, 1, 4] since it is at the deepest level. The algorithm backtracks to that node and then generates another full tour [0, 2, 1, 4, 3] also with cost 41. This allows some of the nodes to be pruned when they are taken off the PQ since their lower bounds are greater than 41.

You may wish to continue this process for this example.

In the next section, we look at the implementation of this algorithm.

18.2 Branch-and-Bound Implementation

One of the most important functions needed to support this branch-and-bound algorithm is the computation of a lower bound for a given tour. This function is as follows:
func LowerBound(tour []int) float64 {
    edges := make([]float64, 0)
    sum := 0.0
    n := len(tour)
    for city := 0; city < NUMCITIES; city++ {
        for index := 0; index < NUMCITIES; index++ {
            // index is part of tour
            found, pos := In(city, tour)
            if n > 1 && found {
                if pos == n-1 {
                    edges = append(edges,
                                graph[city][0])
                } else {
                    edges = append(edges,
                                graph[city][tour[pos+1]])
                }
                break
            }
            found, _ = In(index, tour)
            if n == 1 || !found {
                // Don't allow an index already in
                // tour
                edges = append(edges,
                            graph[city][index])
            }
        }
        sum += Minimum(edges)
        edges = make([]float64, 0)
    }
    return sum
}

The function works exactly as specified in the outline of the algorithm presented in Section 18.1.

A key support function is In given as follows:
func In(value int, values []int) (bool, int) {
    // Returns true if value in values
    // Returns index of location or -1 if not found
    for index := 0; index < len(values); index++ {
        if values[index] == value {
            return true, index
        }
    }
    return false, -1
}

Implementation of Priority Queue

The priority queue plays a central role in this algorithm. It stores nodes, each containing a tour, a lower bound, and a level with priorities defined as specified in Section 18.1 and repeated here for your convenience:

  • Nodes at a deeper level (higher level number) have priority over nodes at a shallower level in the PQ.

  • Priority is given to the node with the smallest lower bound if the nodes are at the same level.

  • If two nodes at the same level have the same lower bound, we add up the cities in the node’s tour, and the node with the higher sum has a higher priority.

The code that supports the implementation of the priority queue is given as follows:
type Node struct {
    tour       []int
    lowerBound float64
    level      int
}
type Nodes []Node
// Allow nodes to be sorted
func (nodes Nodes) Len() int {
    return len(nodes)
}
func (nodes Nodes) Swap(i, j int) {
    nodes[i], nodes[j] = nodes[j], nodes[i]
}
func (nodes Nodes) Less(i, j int) bool {
    if nodes[i].level > nodes[j].level {
        return true
    }
    if nodes[i].level == nodes[j].level &&
        nodes[i].lowerBound == nodes[j].lowerBound {
        // Return the smaller sum of cities
        tour1 := nodes[i].tour
        sum1 := 0;
        for i := 0; i < len(tour1); i++ {
            sum1 += tour1[i]
        }
        tour2 := nodes[j].tour
        sum2 := 0;
        for i := 0; i < len(tour2); i++ {
            sum2 += tour2[i]
        }
        return sum1 < sum2
    }
    if nodes[i].level == nodes[j].level &&
        nodes[i].lowerBound != nodes[j].lowerBound {
        return nodes[i].lowerBound <
                    nodes[j].lowerBound
    }
    return false
}
type PriorityQueue struct {
    items Nodes
}
func NewPriorityQueue() PriorityQueue {
    return PriorityQueue{}
}
func (pq *PriorityQueue) Insert(node Node) {
    tourToInsert := DeepCopy(node.tour)
    nodeToInsert := Node{tourToInsert, node.lowerBound,
                            node.level}
    pq.items = append(pq.items, nodeToInsert)
    sort.Sort(pq.items)
}
func (pq *PriorityQueue) Remove() Node {
    result := pq.items[0]
    pq.items = pq.items[1:]
    return result
}

The priority queue (PQ) holds entities of type Node. Each time we insert a new node into the queue, we sort the queue to ensure that the node with the highest priority is at the front of the queue.

To enable the sorting of nodes in the PQ, we need to implement the interface to the Sort method from package sort.

This is accomplished with the functions Len, Swap, and Less as given earlier. Each of the three priority rules is implemented in the function Less.

The Insert function sorts the items (slice of Node) after appending the node being inserted.

Generating Branch-and-Bound Solution

The function that generates nodes according to the outline from Section 18.1, inserts them into the priority queue, finds best new tours, and backtracks while pruning nodes whose lower bound exceeds the known best tour to date is given as follows in function TSP:
func TSP() {
    var elapsed time.Duration
    start := time.Now()
    bestTour := []int{}
    for i := 0; i < NUMCITIES; i++ {
        bestTour = append(bestTour, i)
    }
    pq := NewPriorityQueue()
    bestCost := LowerBound(bestTour)
    tour := []int{0}
    lowerBound := LowerBound(tour)
    node := Node{tour, lowerBound, 0}
    nodesGenerated += 1
    pq.Insert(node)
    for {
        if len(pq.items) == 0 {
            break
        }
        top := pq.Remove()
        topLevel := top.level
        topTour := top.tour
        // Generate nodes at topLevel + 1
        for i := 0; i < NUMCITIES; i++ {
            tour := DeepCopy(topTour)
            found, _ := In(i, topTour)
            if !found {
                tour = append(tour, i)
                nodesGenerated += 1
                if nodesGenerated %
                        10_000_000 == 0 {
                    fmt.Println(" Nodes generated (in
                    millions): ", nodesGenerated /
                                     1_000_000)
                    fmt.Printf(" Optimum tour cost:
                    %0.2f   Best tour: %v", bestCost,
                    bestTour)
                    elapsed = time.Since(start)
                    seconds := elapsed / 1_000_000_000
                    rate := float64(nodesGenerated) /
                             float64(seconds)
                    fmt.Printf(" Nodes generated per
                    second: %0.0f  Length of PQ: %d
                    Time elapsed: %v", rate,
                    len(pq.items), elapsed)
                }
                if len(tour) == NUMCITIES {
                    // A complete tour is obtained
                    tourCost := LowerBound(tour)
                    if tourCost < bestCost {
                        bestTour = tour
                        bestCost = tourCost
                        fmt.Println(" Best cost of
                        tour so far: ", bestCost)
                    }
                } else {
                    tourCost := LowerBound(tour)
                    if tourCost < bestCost {
                        node := Node{tour, tourCost,
                                  topLevel + 1}
                        pq.Insert(node)
                    }
                }
            }
        }
    }
    fmt.Printf(" Optimum tour cost: %0.2f   Best
    tour: %v   Nodes generated: %d", bestCost,
    bestTour, nodesGenerated)
}
Listing 18-1 puts all the pieces together and shows all the support functions and a main driver that attempts to solve a 33-city problem.
package main
import (
    "fmt"
    "sort"
    "time"
)
const (
    NUMCITIES = 33
)
type Node struct {
    tour       []int
    lowerBound float64
    level      int
}
type Graph [][]float64
var graph Graph
var nodesGenerated int64
type Nodes []Node
// Allow nodes to be sorted
func (nodes Nodes) Len() int {
    return len(nodes)
}
func (nodes Nodes) Swap(i, j int) {
    nodes[i], nodes[j] = nodes[j], nodes[i]
}
func (nodes Nodes) Less(i, j int) bool {
    // Snip
}
type PriorityQueue struct {
    items Nodes
}
func NewPriorityQueue() PriorityQueue {
    return PriorityQueue{}
}
func (pq *PriorityQueue) Insert(node Node) {
    // Snip
}
func (pq *PriorityQueue) Remove() Node {
    // Snip
}
func DeepCopy(tour []int) []int {
    result := []int{}
    for i := range tour {
        result = append(result, tour[i])
    }
    return result
}
func Minimum(values []float64) float64 {
    // This function excludes value 0
    min := 100000000.0
    for i := 0; i < len(values); i++ {
        if values[i] != 0 && values[i] < min {
            min = values[i]
        }
    }
    if min == 100000000.0 {
        return 0.0
    }
    return min
}
func In(value int, values []int) (bool, int) {
    // Snip
}
func LowerBound(tour []int) float64 {
    // Snip
}
func TSP() {
    // Snip
}
func main() {
    graph = // Download from publisher’s website
    TSP()
}
Listing 18-1

Branch-and-bound solution to TSP

Data for main

The graph is constructed from data taken from a Rand McNally Atlas of 33 US cities with distances between them specified.

The details in main are omitted here because of limited space. Please download the entire listing from the publisher’s website.

The known solution to this problem is an optimum tour of 10,861 miles.

Results

After running the branch-and-bound program for 18 hours and 42 minutes and generating 4.6 billion nodes at about 70,000 nodes per second, the best tour generated so far is

[0 13 1 2 3 5 4 6 7 8 9 10 11 17 18 19 27 29 30 28 31 32 22 21 23 24 25 26 20 14 15 16 12]

This tour is 11,553 miles, which is an error of about 6 percent. We must remind ourselves that the total number of nodes in the full tree representing this problem is 263,130,836,933,693,530,167,218,012,160,000,000 nodes.

At an average rate of 71,874 nodes per second, it would take about 1.39 × 1030 seconds or about 4.41 × 1022 years to generate all the leaf nodes in this tree.

18.3 Summary

We presented a branch-and-bound algorithm that provides an exact solution to the TSP. The problem is that this is a computationally intractable problem. If allowed to run long enough, it will find an exact solution to the problem.

A priority queue is used to hold a sequence of nodes, where each node contains a tour (may be a partial tour), a lower bound, and a level. The nodes are sorted in the queue by level, lower bound, and, in the case of a tie, sum of city values in the tour.

A 33-city problem is attempted. After two hours of computation, the best tour obtained is about 6 percent higher than the known optimum tour. This best tour so far remains the same after 16 hours.

This sets the stage for the next two chapters in which we present heuristic solutions to the TSP. These heuristic solutions execute in a matter of seconds and produce solutions that are either exact or have small error.

The next chapter presents a heuristic algorithm, simulated annealing.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.145.178.157