In this project, you will explore the difficulty in choosing a heuristic for a problem using the software package TRAVEL. There is a copy in the course folder on the computer network.
Recall that the chip placement problem can be closely modeled as a traveling salesman problem. As a first approximation, we can ignore the feeder aspects of the chip placement machine and treat the placements as being in the euclidean plane. Our goal in this project is to decide on a heuristic technique to use for this machine.
The problem is defined as follows:
Currently, the system used is to take six random solutions and do 2-opting on each. The best resulting solution is the overall result. Using TRAVEL, try to determine a better mix of heuristics that results in the best average solution. In your report, compare your suggested mix with the current method. Some aspects of your decision that you might want to include in your report include:
You are welcome to use techniques included in TRAVEL that we have not discussed in class (like Lin-Kernighan and SCOTCH).
To complete the project, we would like to know how much more improvement might be expected by better heuristics (like allowing more time). Using the minimum spanning tree and dual ascent relaxations, determine how far from optimal the your ``average'' heuristic solution is.