INEN628: Combinatorial Optimization
Computer Group Project
Objective: Your objective is to implement a graph based
branch and bound computer code to solve the Traveling Salesman Problem
(TSP).
Due
Date: December 5th! The research report and a 10 minute presentation
should be given in class and the source files should be mailed to me at
Minimum
Requirements (100 points): Lower bounds will be
calculated by Held-Karp and the minimum requirement for a starting upper bound
will be calculating a tour with the nearest-neighbor algorithm with
improvements by the Lin-Kernighan algorithm.
Also, the code has to be written in C or C++ (no templates!). Since the
code is in C, numbers start counting at 0 instead of 1.
I/O
Requirements: The code must read in a file through standard
input. The input file will look like the
following:
n m //# of nodes and # of edges
end1
end2 weight //for edge(0)
. .
.
end1
end2 weight //for edge(m-1)
Standard
output must be the ends of the edges chosen with their cost and the cost of the
best tour found like the following:
end1
end2 weight //for edge(0) of tour
. .
.
end1
end2 weight //for edge(n-1) of tour
The
cost of the best tour is: (the cost the
best tour)
Test
Instances: The test instance files will
be sent by email to you. Below are the
names and the optimal costs of the tours:
att48:
10628 berlin52: 7542 gr21: 2707
hk48: 11461 ulysses22: 7013
The
Research Report: The group must also turn in a
detailed report entailing an intro, a description of the problem, the steps of
your algorithm, computational results (i.e. running times) of your code on the
five problems and concluding remarks.
References would be welcomed.
Also email me a critique (5 highest to 1 lowest) of your group members
and their participation in the project.
Extra
Points: Extra points will be given to groups who enhance
the code by adding the advanced algorithm of Christofides
(20 points) to the code.
Technical
Support: There are C primers
in the computer labs (no templates!). Good
luck!