# Connexions

You are here: Home » Content » Introducing a Triplet Formulation to the Traveling Salesman Problem

### Recently Viewed

This feature requires Javascript to be enabled.

# Introducing a Triplet Formulation to the Traveling Salesman Problem

Module by: Marissa Lawson, Lyon Anderson. E-mail the authorsEdited By: Lyon AndersonTranslated By: Lyon Anderson

Summary: The objective of our research is to introduce a new formulation to model the Traveling Salesman Problem, a combinatorial optimization problem.

## The Traveling Salesman Problem

### Background

The problem gets its name from the challenges faced by salesman who traveled town-to-town selling their wares. These salesmen needed to take a route that was most efficient in terms of time or distance. The problem can be stated as follows: Given a collection of cities and the cost of travel between each pair of them, the traveling salesman problem is to find the cheapest way of visiting all of the cities and returning to your starting point, [1].

### Linear Program

This can be modeled by the following objective function and constraints:

min i = 1 n j = 1 , j i n c i j x i j min i = 1 n j = 1 , j i n c i j x i j
(1)

subject to

i = 1 , i j n x i j = 1 j i = 1 , i j n x i j = 1 j
(2)
j = 1 , j i n x i j = 1 i j = 1 , j i n x i j = 1 i
(3)
x i j + x j i 1 x i j + x j i 1
(4)
i , j S n x i j | S | - 1 S { 1 , . . . , n } i , j S n x i j | S | - 1 S { 1 , . . . , n }
(5)

where

cijcij is the cost of going between city ii and city jjxij=1,ifnodejimmediatelyfollowsiinthetour0,otherwisexij=1,ifnodejimmediatelyfollowsiinthetour0,otherwise

These constraints model a directed TSP. (2) Tells us that only one city can come immediately after a specific city in a tour. (3) Tells us that only one city can come immediately before a specific city in a tour. (4) Establishes a direction in our model. The last constraint, (5), known as the subtour elimination constraint, rules out the possibility of two separate tours going through the set of cities. (5) can be inefficient at times, so our goal is to introduce the triplet formulation to replace this constraint and possibly create a more efficient model.

## The Triplet Formulation

### Background

Our approach for modeling the TSP comes from a formulation of the single row facility layout problem (SRFLP). The SRFLP is a problem concerned with arranging departments on a line with the least cost. In a paper discussing the single row facility layout problem, Amaral introduces a new polytope consisting of a set of vectors, ζijkζijk. These binary vectors represent a permutation of departments, [2].

ζ i j k = 1 , if department k lies between departments i and j 0 , otherwise ζ i j k = 1 , if department k lies between departments i and j 0 , otherwise
(6)

We refer to this as the triplet formulation. With the TSP, ζζ is defined in the following way:

ζ i j k = 1 , if city k lies between city i and j in the tour 0 , otherwise ζ i j k = 1 , if city k lies between city i and j in the tour 0 , otherwise
(7)

Amaral also introduced a set of facet defining constraints on ζζ. In our work we consider these constraints and modify them so that they adequately model the traveling salesman problem.

### Constraints from the Triplet Formulation

Amaral introduces a set of valid inequalities that model the SRFLP in [2]. By working through examples, we are able to modify these inequalities to model the TSP. The following inequalities are true for our directed model of the TSP.

0 ζ i j k 1 0 ζ i j k 1
(8)
ζ i j k ζ j i k ζ i j k ζ j i k
(9)
ζ i j k + ζ i k j + ζ j k i 2 ζ i j k + ζ i k j + ζ j k i 2
(10)
ζ i j d + ζ j k d - ζ i k d 1 ζ i j d + ζ j k d - ζ i k d 1
(11)
ζ i j d + ζ j k d + ζ i k d 3 ζ i j d + ζ j k d + ζ i k d 3
(12)

Each of these constraints establish the possible permutations of cities in our tour.

### Linear Program

We are able to adjust our linear program by throwing out our subtour elimination constraint, (5), and adding the constraints on ζζ along with a linking constraint, (21).

min i = 1 n j = 1 , j i n c i j x i j min i = 1 n j = 1 , j i n c i j x i j
(13)

subject to

i = 1 , i j n x i j = 1 j i = 1 , i j n x i j = 1 j
(14)
j = 1 , j i n x i j = 1 i j = 1 , j i n x i j = 1 i
(15)
x i j + x j i 1 x i j + x j i 1
(16)
0 ζ i j k 1 0 ζ i j k 1
(17)
ζ i j k ζ j i k ζ i j k ζ j i k
(18)
ζ i j k + ζ i k j + ζ j k i 2 ζ i j k + ζ i k j + ζ j k i 2
(19)
ζ i j d + ζ j k d - ζ i k d 1 ζ i j d + ζ j k d - ζ i k d 1
(20)
ζ i j d + ζ j k d + ζ i k d 3 ζ i j d + ζ j k d + ζ i k d 3
(21)
x i j + ζ i j k 1 i , j , k x i j + ζ i j k 1 i , j , k
(22)

## Results

After creating a program in C++ we were able to optimize small instances of the TSP using Gurobi. Introducing ζζ and its constraints effectively eliminated subtour solutions. Our code includes a nearest neighbor algorithm as well as a Lin-Kernighan algorithm. These algorithms were used to introduce an upper bound on our objective function, and reduce run time. While our smaller examples (number of nodes << 22) were able to run to completion, larger examples were killed before the optimal tour was found.

## Future Work

In the future, we would like to revise our formulation to reduce run time. In particular, we would like to try to model this problem without using direction. Eliminating direction would remove several variables and possibly reduce run time.

## Acknowledgments

We would like to thank Dr. Hicks and Dr. Susan Margulies for their guidance throughout our research. Our work was funded by the NSF.

## References

1. http://www.tsp.gatech.edu/index.html

2. A. R. S Amaral, A New Lower Bound for the Single Row Facility Layout Problem, Discrete Applied Mathematics 157 (1) (2009) 183-190.

## Content actions

PDF | EPUB (?)

### What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks