Abstract
The chapter presents a traveling salesman problem, its network properties, convex quadratic formulation, and the solution. In this chapter, it is shown that adding or subtracting a constant to all arcs with special features in a traveling salesman problem (TSP) network model does not change an optimal solution of the TSP. It is also shown that adding or subtracting a constant to all arcs emanating from the same node in a TSP network does not change the TSP optimal solution. In addition, a minimal spanning tree is used to detect sub-tours, and then sub-tour elimination constraints are generated. A convex quadratic program is constructed from the formulated linear integer model of the TSP network. Interior point algorithms are then applied to solve the TSP in polynomial time.
TopIntroduction
The traveling salesman problem (TSP) was believed to be difficulty until now (Munapo, 2020) or (Papadimitriou, 1977) or (Berman & Karpinski, 2006). The TSP has so many applications which include scheduling, sequencing, vehicle routing, engineering, electronics and genetics. In this paper it is shown that adding or subtracting a constant to all arcs with special features in a traveling salesman problem (TSP) does not change an optimal solution of the (TSP). It is also shown that adding or subtracting a constant to all arcs emanating from the same node in a TSP network does not change the TSP optimal solution. A minimal spanning tree (Wolsey, 1989) is used to detect sub-tours and then sub-tour elimination constraint generated (Bektas & Gouveira, 2006). A convex quadratic program (Jensen & Bard, 2003) is constructed from the formulated linear TSP integer model. Interior point algorithms (Gondzio, 2012) are then applied to solve the TSP in polynomial time.
The TSP Model
The objective is to start from an origin node and return to it, traversing the nodes in such a way that every node is visited once and that the total distance travelled is minimized (Applegate et al. 2006) or (Gutin & Punnen, 2006). It is also assumed that all nodes have at least two arcs emanating from them.
Available Methods
Exact Approaches
There are several exact approaches that are currently available for the TSP. These include:
- a)
Brute force. In this approach we try all possible routes and see which one is the cheapest and the worst case complexity is O(n!) and is not practical for large number of nodes.
- b)
Linear programming based branch, cut and price methods. See Padberg & Rianld (1991), Mitchell (2001), or Nadef (2002) for more on branch and cut methods.
- c)
Branch and bound method in which assignment sub-problems are used (Winston, 2004).
- d)
Dynamic programming techniques (Winston, 2004).
A lot of effort has been injected into these exact approaches and a consistent efficient method is now available.
Heuristics
These are methods that quickly give solutions that are close to optimal solution (Winston, 2004). The problem with these heuristics is that the difference between the exact solution and the near optimal solution is sometimes very big. In terms of money it means millions of dollars for the large real life problems.
Direct Linear Programming Based Approach
It is easy to directly formulate the TSP as an LP and solve using the available interior point algorithms to obtain an optimal solution in polynomial time. Unfortunately direct LP formulation has a serious challenge. The challenge is that the optimal solution contains sub-tours as illustrated in the following example.
Key Terms in this Chapter
Optimal Solution: A feasible solution at the point where the objective function reaches its maximum/minimum value.
TSP: Is the traveling salesman problem (TSP) where we move from an origin node and return to it, traversing the nodes in such a way that every node is visited once and that the total distance travelled is minimized.
Branch and Bound Method: This is a solution method which partitions the feasible solution space into smaller subsets of solutions.
Principal Minor: A principal submatrix of a square matrix A is the matrix obtained by deleting any k rows and the corresponding k columns.
Hessian Matrix: Is a square matrix of second-order partial derivatives which describes the local curvature of a function of many variables.
Algorithm: A procedure or set of rules to be followed in problem-solving operations, specifically by a computer.
Sub-Tour: Given any n nodes, any connection of nodes made of up k nodes where k is less than n , is called a sub-tour. The connection is such that when visiting the nodes each node is visited once and we return to the initial node.
Tour: Is a traversal of each node exactly once that returns to the initial node. The cost of a tour is the sum of the distance between each pair of nodes on the tour.
Objective Function: Is a mathematical expression that minimizes or maximizes a linear or nonlinear problem.
Heuristic: Is a mental shortcut that allows people to solve problems and make judgments quickly and efficiently.
Positive Definite: A square matrix H is positive definite if Y T HY >0, ? Y ?0.
MST: Given any n set of nodes, a minimal spanning tree (MST) is the network of arcs that connects all the n nodes.