Branch and Bound Algorithm to Solve the Traveling Salesman Problem

In this blog post, we are going to take a look at how to use the Branch and Bound algorithm to solve the Traveling Salesman Problem and how to implement it using ruby.

First what is Branch and Bound algorithm? according to geeksforgeeks The Branch and Bound Algorithm is a method used in combinatorial optimization problems to systematically search for the best solution. It works by dividing the problem into smaller subproblems, or branches, and then eliminating certain branches based on bounds on the optimal solution. This process continues until the best solution is found or all branches have been explored.

Branch and Bound is commonly used to solve many problems like the Assignment Problem, Vehicle Routing Problem, Traveling Salesman Problem, Telecommunications Network Design, etc. But in this article we will use the Branch and Bound algorithm to solve the Traveling Salesman Problem and we'll implement it using ruby.

Before we dive deeper into the details let me give you an insight about what is the Traveling Salesman Problem.

Wikipedia says that the travelling salesman problem, also known as the travelling salesperson problem (TSP), asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

As said Wikipedia we'll give a list of cities and the distances between each pair of cities, the task is to find the shortest possible route that visits each city exactly once and returns to the origin city.

In other words, the goal is to determine the most efficient route for a salesman to visit a set of cities and return to the starting point, minimizing the total distance traveled.

Analyzing the above problem here are the steps we want to follow to solve the problem:

1. Initialization:

• Represent the problem as a weighted graph G=(V,E), where 𝑉 is the set of cities and 𝐸 is the set of edges (roads) connecting the cities.
• Define an initial solution (usually a random tour) and calculate its total distance.
• Create a priority queue (or any other suitable data structure) to store the partial solutions.

require 'priority_queue'

class TravellingSalesmanProblem
  def initialize(cities)
    @cities = cities
    @graph = build_graph(cities)
    @best_tour = nil
    @best_distance = Float::INFINITY
    @priority_queue = PriorityQueue.new
    @priority_queue.push([], 0)
  end

  private

  def build_graph(cities)
    graph = {}
    cities.each do |city|
      graph[city] = cities.reject { |c| c == city }.map { |c| [c, distance(city, c)] }.to_h
    end
    graph
  end

  def distance(city1, city2)
    # Calculate the distance between two cities
    # (e.g., using Euclidean distance)
    Math.sqrt((city1[0] - city2[0])**2 + (city1[1] - city2[1])**2)
  end
end 

2. Lower Bound Calculation:

• For each partial solution in the priority queue, calculate a lower bound on the total distance of the complete tour.
• One common way to calculate the lower bound is to find the minimum spanning tree of the remaining unvisited cities and add the cost of the minimum spanning tree to the current partial tour's distance.

def lower_bound(tour)
  unvisited_cities = @cities - tour
  return Float::INFINITY if unvisited_cities.empty?

  total_distance = tour.sum { |city| @graph[city].values.min }
  unvisited_cities.each do |city|
    total_distance += @graph[city].values.min
  end
  total_distance
end

3. Branching:

• Select the partial solution with the smallest lower bound from the priority queue.
• For each unvisited city in the selected partial solution, create a new partial solution by adding the city to the tour.
• Calculate the lower bound for each new partial solution.

def branch_and_bound
  until @priority_queue.empty?
    tour, distance = @priority_queue.pop
    return tour if tour.length == @cities.length

    unvisited_cities = @cities - tour
    unvisited_cities.each do |city|
      new_tour = tour + [city]
      new_distance = distance + @graph[tour.last][city]
      new_lower_bound = lower_bound(new_tour)
      @priority_queue.push(new_tour, new_lower_bound)
    end
  end
  @best_tour
end

4. Pruning:

• Compare the lower bound of each new partial solution with the current best solution's total distance.
• If the lower bound of a partial solution is greater than or equal to the current best solution's total distance, discard that partial solution (i.e., prune the branch).

5. Update the Best Solution:

• If a new partial solution's total distance is less than the current best solution's total distance, update the best solution.

def branch_and_bound
  until @priority_queue.empty?
    tour, distance = @priority_queue.pop
    return tour if tour.length == @cities.length

    if distance < @best_distance
      @best_tour = tour
      @best_distance = distance
    end

    # ... rest of the branch_and_bound method
  end
  @best_tour
end

6. Repeat:

• Repeat steps 2 to 5 until the priority queue is empty or a stopping criterion is met (e.g., a time limit, a maximum number of iterations, or the optimal solution is found).

7. Output the Result:

• The final best solution represents the optimal Traveling Salesman tour.

cities = [[0, 0], [1, 1], [2, 0], [3, 1]]
tsp = TravellingSalesmanProblem.new(cities)
optimal_tour = tsp.branch_and_bound
puts "Optimal tour: #{optimal_tour}"
puts "Optimal distance: #{tsp.best_distance}"

Here's the complete code:

require 'priority_queue'

class TravellingSalesmanProblem
  def initialize(cities)
    @cities = cities
    @graph = build_graph(cities)
    @best_tour = nil
    @best_distance = Float::INFINITY
    @priority_queue = PriorityQueue.new
    @priority_queue.push([], 0)
  end

  def branch_and_bound
    until @priority_queue.empty?
      tour, distance = @priority_queue.pop
      return tour if tour.length == @cities.length

      if distance < @best_distance
        @best_tour = tour
        @best_distance = distance
      end

      unvisited_cities = @cities - tour
      unvisited_cities.each do |city|
        new_tour = tour + [city]
        new_distance = distance + @graph[tour.last][city]
        new_lower_bound = lower_bound(new_tour)
        @priority_queue.push(new_tour, new_lower_bound)
      end
    end
    @best_tour
  end

  private

  def build_graph(cities)
    graph = {}
    cities.each do |city|
      graph[city] = cities.reject { |c| c == city }.map { |c| [c, distance(city, c)] }.to_h
    end
    graph
  end

  def distance(city1, city2)
    # Calculate the distance between two cities
    # (e.g., using Euclidean distance)
    Math.sqrt((city1[0] - city2[0])**2 + (city1[1] - city2[1])**2)
  end

  def lower_bound(tour)
    unvisited_cities = @cities - tour
    return Float::INFINITY if unvisited_cities.empty?

    total_distance = tour.sum { |city| @graph[city].values.min }
    unvisited_cities.each do |city|
      total_distance += @graph[city].values.min
    end
    total_distance
  end
end

cities = [[0, 0], [1, 1], [2, 0], [3, 1]]
tsp = TravellingSalesmanProblem.new(cities)
optimal_tour = tsp.branch_and_bound
puts "Optimal tour: #{optimal_tour}"
puts "Optimal distance: #{tsp.best_distance}"

This implementation uses the priority_queue gem to manage the partial solutions.