Combinatorial Optimization: The Traveling Salesman Problem
MetadataShow full item record
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.