Next: Solutions to Some Optional
Up: A Tutorial on Integer
Previous: Cuts for Special Structure
We have seen a couple of ways of solving hard integer programs.
Depending on the application, these algorithms may be fast to find an
optimal solution or, on the contrary, prohibitively time consuming for
a computer. For example we know that, in some cases, branch and bound
can take an enormous amount of time. When it is impractical to compute
an optimal solution, one has to settle for a good (but not necessarily
optimal) solution. Such solution procedures are called heuristic
methods or heuristics. Heuristics often have an intuitive
justification but they are not guaranteed to produce an optimal
solution nor even a good solution, in many cases.
In this chapter, we illustrate the heuristic approach on the traveling
salesperson problem. Remember that the problem is the following. A
traveling salesperson must visit once each of n cities before
returning home. He knows the distance between each of the cities and
wishes to minimize the total distance traveled. In what order should
he visit the cities? We have seen in earlier chapters that, although
this problem can in principle be solved by branch and bound combined
with cutting planes or by dynamic programming, the time required to
find an optimal solution may explode exponentially as the number of
cities n becomes large. This is an ideal situation for trying
heuristics.
There are two main types of heuristics for the traveling salesperson problem:
those that construct a tour from scratch and those that improve on a previously
obtained solution.
Tour Construction Heuristics
- Nearest neighbor: A starting city is chosen at random and then a tour is
constructed by going from the current city to the nearest city which has not yet
been visited. When the last city is reached, the path returns to the starting
city, thereby completing the tour.
- Nearest insertion: This heuristic starts with a tour that visits two
cities very close together. Then the remaining cities are inserted one at a time
by removing one edge of the existing tour and linking in the new city between
the two ends. The next
city to be introduced at each stage is chosen to be one which increases the
length of the tour by the smallest possible amount.
- Furthest insertion: This heuristic starts with a tour that visits
two cities which are furthest apart. The next
city to be inserted is the one that increases the
length of the current tour the most when this city is inserted
in the best position on the current tour. The rationale behind the furthest
insertion heuristic is that some
cities will be expensive to insert and we might as well bite the bullet early
since all cities have to be visited eventually.
- Sweep:
This heuristic locates the center of the map and then rotates a
half line around this center. The cities are visited in the order in which they
are met by the line as it sweeps around the center point. This is the only tour
construction heuristic which will guarantee a noncrossing tour for points in
the plane.
Tour Improvement Heuristics
- Two-opt: This heuristic systematically looks at each pair of
nonadjacent edges of the current tour and determines whether the tour length
would be decreased by removing these two edges and adding the other possible
pair of edges which would result in a tour. If so, the exchange is performed
and the search for an improving pair of edges continues. This will result in
a noncrossing tour for points in the plane. Moreover, a noncrossing tour will often have its length
reduced by this heuristic.
- Three-opt: This is similar to the two-opt heuristic, except that now
three edges are removed and the resulting three tour segments are recombined
to form a tour.
- Lin-Kernighan: This is a powerful interchange heuristic which proceeds
as follows. An edge is removed from the current tour, thereby producing a path.
Then one end of this path is joined to some internal node and an edge is
removed, thereby yielding a new path. This add/remove operation is then repeated. Let the "gain sum" be the sum of
the lengths of the removed edges (except the last) minus the sum of the lengths
of the added edges. The add/remove operation continues as long as the gain sum
is positive and there still remain unadded/unremoved edges. For each path
constructed, the cost of the tour obtained by joining its endpoints is also
computed and if it is less than that of the original tour, we keep track of this improved solution.
Then when a sequence of possible interchanges has been exhausted, if an
improvement was found at any point, the best tour found replaces the original
tour and the procedure is repeated.
Next: Solutions to Some Optional
Up: A Tutorial on Integer
Previous: Cuts for Special Structure
Michael A. Trick
Sun Jun 14 12:49:07 EDT 1998