next up previous contents
Next: Spanning Tree Relaxation Up: An application oriented tutorial Previous: HeuristicsRelaxations, and Branch

Relaxations

A relaxation is a solution to a related problem that gives a lower bound (for maximization) on the solution to the problem of interest. In general, a relaxation ignores certain constraints on a problem in order to get an easy-to-solve problem.

While good heuristics are a dime a dozen for most problems, good relaxations are a lot harder to find. Here are three relaxations for the TSP.





Michael A. Trick
Mon Nov 11 15:16:52 EST 1996