## Combinatorial Optimization: The Traveling Salesman Problem

##### Abstract

Optimization is the process of finding the best (or optimal)
solution to a problem. For many real-world problems. there may be a
large number of possible solutions, even an infinite number.
Optimization seeks to find the solution that either maximizes or
minimizes the problem. In these types of problems. it is assumed
that the value of any solution to a given problem can be measured in
a quantifiable way and this value can be compared with that of any
other solution to the problem.
Problems such as this have arisen since the beginning of
mankind. One such example is recorded by Virgil in his Aeneid
where he relates the dilemma of Queen Dido. who was to be given all
the land she could enclose with the hide of a bull. She started by
cutting the hide into thin strips and joining them together. she
formed a semicircle inside of which she enclosed a large section of
land with the Mediterranean coast as the diameter. Archimedes
later conjectured that her solution was mathematically optimal;
which says. a semicircle. together with a straight line. is the curve
of fixed length which will enclose the largest possible area. This
problem just described has an infinite number of possible answers.
as there is an infinite number of possible curves of any given length.
There exist a set of optimization problems that have only a finite
number of solutions. This set of problems along with the theory and
techniques associated with them is known as "combinatorial
optimization". There are many famous optimization problems, but I
will focus on one of them, namely the traveling salesman problem.
Before I discuss that problem, I would like to examine a simple kind
of optimization problem that uses linear programming. In
conclusion, I will examine another kind of optimization problem
from the field of Operations Research. This problem simply shows
another optimization technique.