TSP - Travelling Salesman Problem

Introduction

• I will talk about P vs NP, NP-complete, and NP-hard, define heuristics in computer science, Hamiltonian cycles, TSP and Metric TSP, approximation algorithms, and optimal vs suboptimal solutions. I will also mention local minima, combinatorial explosion, and why exact solutions become infeasible. Finally, we will see an optimal solution and also an approximation algorithm.
• I’ll also discuss the limitations of the chosen approximation algorithm, what could be improved, and mention other options like MST-based solutions, k-opt methods, and metaheuristics such as genetic algorithms, and their trade-offs.
• The project code and analysis were developed in collaboration with Matheus Persch as part of the DSA III class at Federal University of Pelotas (UFPel), Brazil.

Prerequisites

Types of problems

• Decision problem: You want to answer yes or no.
  • E.g. “Is there any Hamiltonian cycle in this graph G?” (YES/NO)
• Search problem: You want to find a valid solution (if it exists).
  • E.g. “Find a Hamiltonian cycle in this graph G.”
• Optimization problem: You want to find the best solution according to some objective (min/max).
  1. “Find the shortest Hamiltonian cycle in this graph G.” (TSP) - minimization problem
  2. “Find the maximum clique in graph G.” - maximization
  3. clique = subset of vertices in a graph that forms a complete subgraph

Time complexity class

• Informal definition: Set of problems solvable in O(TIME(n)) time.
  • Example: sorting is in P because it has polynomial-time algorithms.
• Formal definition: TIME(t(n)) is the set of languages decidable by a deterministic Turing machine in O(t(n)) time.
  • Note: “decidable” is formal for languages; for problems like sorting, this feels unnatural, so focus on the informal version for now.

P, NP, NP-Complete, NP-Hard

• Polynomial time (P): Those problems which are decidable in polynomial time using a deterministic Turing machine.
  • TIME(O(n^k)) → k constant
• Nondeterministic Polynomial time (NP): Those decision problems whose solutions can be verified in polynomial time by a deterministic Turing machine.
  • Verification: Given a candidate solution (certificate), we check if it is valid.
  • E.g. “Given a graph and a certificate, check if it is a valid Hamiltonian cycle.”
• NP-Complete (NPC):
  1. is NP
  2. Every problem in NP can be reduced to it in polynomial time
     • One example is the SAT
• NP-Hard: Problems that are at least as hard as the hardest problems in NP.
  1. Every problem in NP can be reduced to them in polynomial time
  2. Not required to be in NP
     1. ALL NP-complete are NP-hard
     2. But not all NP-hard problems are NP-complete
  3. NP-hard problems are not restricted to be decision problems such as P, NP and NPC.
  4. Example: TSP (optimization version)
• For more detailed explanations, read the chapters of Michael Sipser’s book or watch his lectures in the references of this post.

• Image reference: Wikipedia NP-hardness

What is the Traveling Salesman problem?

• Hamiltonian cycle Problem = Does a cycle exist that visits every vertex exactly once?
  • Note: you can't repeat the same edge, but there are variations where you can do it.
• TSP = Among all Hamiltonian cycles, which one has minimum cost?

Metric TSP

• Metric TSP is formulated on a complete graph with distances satisfying the triangle inequality.
• Metric TSP contains the following properties:
  • nodes= (x,y,z); distance = d
  • d(x,y) ≥ 0 (not negative)
  • d(x,y) = d(y,x) (symmetric → undirected)
  • d(x,y) + d(y,z) ≥ d(x,z) (triangle inequality)

• Image reference: https://www.onlinemathlearning.com/triangle-inequality.html
• This ensures that for a path a -> b -> c, replacing it with the direct edge a -> c will never increase the cost. It will stay the same or decrease.

Why finding the optimal TSP solution is infeasible in practice

• Because it is NP-hard, it means there is no known polynomial-time solution for it.
• There are multiple exact (optimal) algorithms, but brute force is the simplest and has time complexity of O(n!)
  • Example: n = 40 n! ~= 8.1591528 * 10^47 ~= 10^47 tours required
  • Imagine you can compute 1 billion tours per second: 10^9 tours
  • 10^47 / 10^9 = 10^38 seconds ~= 3 * 10^30 years required to run it
  • age of universe ^= 13.8 * 10^10 years
  • It would take far longer than the age of the universe.
• What I’ve shown above is called “combinatorial explosion”.
  • For first city you have n options
  • For second you have n-1 options
  • And so on
  • It is factorial: n * (n - 1) * (n - 2) * ... * 1 = n!

How to solve something that requires this amount of time?

• As mentioned, it would require literally more time than is possible in this universe for a small n. To solve this type of problem, one possible approach is using approximation algorithms, which will provide you an approximate solution instead of the optimal one.

Heuristics in Computer Science

• Hromkovič, J. (2004), Chapter 6, defines: ‘A heuristic algorithm in a very general sense is a consistent algorithm for an optimization problem that is based on some transparent (usually simple) strategy of searching in the set of all feasible solutions, and that does not guarantee finding any optimal solution’.
• They must be much faster than the optimal solution, otherwise you would choose the optimal one.
• Types of heuristics:
  • Constructive: Build a solution following a set of pre defined rules.
  • Improvement: Start with a feasible solution (any one), and apply successive small changes to improve it.
  • Compound: Use both, constructive solution and then an improvement phase.

Approximation algorithms

• If an optimization problem is NP-hard such as the TSP one, there is no polynomial-time algorithm to solve it, unless P=NP (something we don’t know yet).
  • Optimal solution = the best solution using a non-approximation algorithm, for example, in TSP using brute force to test all possible tours would provide us for sure the cheapest Hamiltonian cycle.
  • Suboptimal solution = an approximate solution, isn’t the optimal one, but is close to it.
• What an approximation algorithm does is exactly this: instead of trying to get an optimal solution for an NP-hard problem until the universe ends, we use an approximation algorithm to achieve an approximate solution with much faster execution time.
• k-approximate approximation algorithm = Means that it is no worse than k times the optimal solution.
  • for minimization: optimal = 1; 2-approximate = 2 (2*opt)
  • for maximization: optimal = 2; 2-approximate = 1 (1/2*opt)
  • As you can see, an approximation algorithm is never better than the optimal; otherwise it would be the optimal one.
  • It can even be equal to the optimal solution in some cases (but not always).
• Note: To develop approximation algorithms we generally use heuristics (defined in the prerequisites).

Optimal solution for the TSP

• There are many optimal solutions, all of them are too slow since this is an NP-hard problem.
• We call brute force solution a solution that relies on exhaustive search.
• The one I'll show you today is the Branch-and-Bound solution, that consists in backtracking plus pruning unnecessary paths before opening them.
• If you don't understand backtracking check this Github (Code) - Backtracking playground

Branch-and-Bound for Metric TSP:

• Branch = check new paths (permutations)
• Bound = check the upper/lower bound and cut if already worse to avoid unnecessary paths
  • lower if is a minimization problem
  • upper if is a maximization problem
• We fix the starting position as 0
• Then we start checking permutations, such as (01230, 02130, 02310, …).
• If we can identify that, before reaching the end, the current path is already worse than our current best, we do not need to continue (prune), and we stop exploring this path.
  1. Since TSP is a minimization problem, if our currCost is already worse than our bestCost (lower bound), there is no reason to continue exploring that path.
• When we reach the end of a path, we return to start and check if currCost < bestCost

Branch-and-Bound code

// Time Complexity: O(V!)
// Space complexity: O(V)
unsigned int Graph::runTSPBranchAndBound(TSPState state) const {
  int pathSize = state.path.size();
  int vertices = getVertices();

  if(pathSize == vertices) {
    int lastUsedPos = state.path.back();
    unsigned int totalCost = state.currCost + getDistance(lastUsedPos, 0);
    return totalCost < state.bestCost ? totalCost : state.bestCost;
  }

  for(int i = 0; i < vertices; i++) {
    if(state.visited[i]) {
      continue;
    }

    // key diff from brute-force version
    int currDist = getDistance(state.path.back(), i);
    int newCost = state.currCost + currDist;
    if(newCost >= state.bestCost) { // cleaning unnecessary paths (prune = Branch-and-Bound)
      continue;
      // if I use a specific graph where pruning never happens, it becomes as bad as brute force because
      // it ends up exploring the entire search space without cutting any branches
      // fortunately, this is not the case in most situations
    }

    state.currCost += currDist;
    state.visited[i] = true;
    state.path.push_back(i);

    state.bestCost = std::min(state.bestCost, runTSPBranchAndBound(state));

    state.path.pop_back();
    state.visited[i] = false;
    state.currCost -= currDist;
  }

  return state.bestCost;
}

• But it is still too slow. Since TSP is an NP-hard problem, we still require an approximation algorithm to get a faster, approximate solution for that problem.

Approximation Algorithm for TSP

• The difference between a heuristic and an approximation algorithm is that an approximation algorithm has a proven bound on how far its solution can be from the optimal one.
• For example, a 2-approximation algorithm guarantees that in the worst case it will return a solution at most twice as bad as the optimal one. This is proven mathematically.
• There are multiple approximation algorithms for the same problem, and this also happens in TSP, where you can solve it using, for example, the MST double-tree algorithm, Christofides algorithm, and more.

The Nearest Insertion Solution (2-approximate algorithm)

• Image reference: Nearest Insertion - (Rosenkrantz, Stearns, Lewis, 1974)
• Code here - Graph::runTSPNearestInsertion()
  • Time Complexity: O(V^2)
  • Space complexity: O(V)

Running Time Comparisons

• Just some examples, on a random computer of ours.

Optimal: time O(V!)

• Branch-And-Bound is already 10x faster than pure brute force for the 11x11 graph. Even though both algorithms have the same worst case, since branch-and-bound prunes some unnecessary paths.
• But as we can see, running it for 15x15 would already take too much time so we didn't.

Approximate: time O(V^2)

• And obviously the approximation is much faster and has a worst-case 2-approximation guarantee, and in our files the worst was not 2 but only ~11.45% worse than the optimal.

Extra: Metaheuristic and Genetic algorithm for TSP

Metaheuristics in Computer science

• A metaheuristic is a high-level framework with some guidelines to build a heuristic (abstract idea to solve high-level).
• A Genetic heuristic is made of:
  1. populations
  2. select
  3. crossover
  4. mutate (small percentage)
  5. improve
  6. repeat
• It still requires problem specific solutions, where we use heuristics, for example:
  • crossover operator (e.g., EAX for TSP)
  • local search heuristics (2-opt, k-opt, …)

Genetic Algorithm with Edge Assembly Crossover (EAX-GA)

• It is a TSP approximation algorithm that does the following:
• Populations
  • N Hamiltonians cycles: [(A→B→C→D→E→A), ham cycle 2, …, ham cycle N]
• Select (parents)
  • Choose randomly X pairs of hamiltonians cycle within your population
• Crossover (Edge Assembly Crossover)
  • Combine the pair parent1 and parent2 (both hamiltonian cycles) to generate a child hamiltonian cycle.
• Mutate
  • Here we select a small rate such as 5% of the generated children and we try to improve them by mutating
• Local Search (apply one heuristic to improve)
  • child = improve_with_2opt_or_LK(child)
• Repeat N times until reaching the stop condition (time or iterations)
  • Now you have a new population of children, you can even get some of the best parents to put in your population and remove the “worst children”.
    • read best as smaller cost and worst as biggest cost to travel
    • “Keep best solutions within parents and children and repeat.”
  • And within this population, select, crossover, mutate, and improve with local search once again until reaching the stop condition.

More solutions for the TSP

• There are multiple solutions for the TSP:
  • 2-opt: swap two edges (small neighborhood), fast but weak
  • k-opt: swap k (constant) edges (larger neighborhood), better solutions, but slower
  • Lin–Kernighan heuristic (LK): adaptive k-opt, usually best trade-off between solution approximation and running time.
  • MST-based: build a Minimum Spanning Tree (MST), then do a preorder DFS traversal and shortcut repeated nodes (works for Metric TSP, gives a 2-approximation)
• Some of those such as the 2-opt stop in the local minimum, it means that it gets stuck with the best local solutions but it doesn’t mean it’s the global optimal solution.
  • That means: for every pair of edges you try to swap, but the total distance does not decrease.
  • It can’t improve anymore but there may exist better solution.
  • The problem isn’t getting stuck in a local minimum, but how good that local minimum is.

References

• Github (Codes) - TSP-Approximation-Algorithm
• Michael Sipser - Introduction to the Theory of Computation, 2nd edition
• Michael Sipser - Theory of Computation MIT
• MIT OpenCourseWare - R9. Approximation Algorithms: Traveling Salesman Problem
• Heuristics and Local Search (José Fernando Oliveira, Maria Antónia Carravilla – FEUP)
• Abdul Bari - 7.3 Traveling Salesman Problem – Branch and Bound
• Nearest Insertion - (Rosenkrantz, Stearns, Lewis, 1974)