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:

• Instances are well approximated by scattering 120 points randomly in a square.
• Any combination of heuristics can be used.
• Each heuristic has a ``value'' based on the amount of time it takes to run. These values are as follows:

• Random Solution: 0
• Nearest Neighbor: 1
• Nearest Insertion: 1
• Farthest Insertion: 2
• Space Filling Curve: 1
• SCOTCH: 2
• Sweep: 1
• 2-opt: 5
• 3-opt: 15
• Lin-Kernighan: 30
• The total value of the combination of heuristics you choose must be no more than 30.

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:

• Robustness: Does your method do well on many instances or does it do well on some and poorly on others?
• Statistical Significance: Is your method better just on average, or can you apply a statistical technique to judge the improvement?

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.