Skip to content
Tutorials Center
My learning

Topics

Lesson 40 of 49 ยท Heuristics and Practice

Construction Heuristics and Local Search

Build good solutions fast with greedy rules, nearest neighbor and knapsack by ratio, then improve them with 2-opt local search, and measure the gap to the optimum.

Two simple ideas power most practical heuristics. The first is construction: build a complete solution one decision at a time, always taking the choice that looks best right now (the greedy idea). The second is local search: start from any solution and keep making small changes as long as each change helps. Used together, they turn an awful-looking problem into one you can solve in a fraction of a second, with answers that are usually within a few percent of the best.

In this lesson you will use both on two classic problems: choosing items for a backpack (the knapsack problem) and planning a round trip (the traveling salesman problem).

Two tours through twelve cities, before and after 2-opt improvement
Caption: The nearest-neighbor tour (left) ends with a long return leg; 2-opt moves uncross and shorten the long edges, giving the tour on the right, about 16 percent shorter.

What you will learn

  • How greedy construction works and why it can be wrong.
  • How to apply the nearest-neighbor rule and a ratio rule for the knapsack.
  • How 2-opt local search improves a tour, and what a local optimum is.
  • How to measure heuristic quality with an optimality gap.

Key terms

Greedy rule: at each step make the choice with the best immediate benefit, never reconsidering.

Neighborhood: the set of solutions reachable from the current one by a single small move.

2-opt move: remove two edges of a tour and reconnect the pieces the other way, which reverses the path between them.

Local optimum: a solution with no better neighbor.

Optimality gap: how far above the best known value a heuristic's value is, in percent.

Greedy construction on a knapsack

You can carry 40 kg. Each item has a value and a weight:

Item Value Weight Value per kg
P 72 12 6.0
Q 110 20 5.5
R 130 25 5.2
S 45 10 4.5

A natural greedy rule: take items in decreasing order of value per kg as long as they fit. P (12 kg), then Q (20 kg, total 32), then R does not fit (it would reach 57 kg), S does not fit (42 kg). The load is worth 182.

Is that the best? Try P and R: 37 kg and value 202. The greedy rule missed it, because taking Q early used up weight in a way that blocked a better combination. Greedy rules are fast and often good, but they never look back. For knapsack-type problems the exact answer can be found by dynamic programming when weights are small whole numbers, but for huge instances or complicated side conditions greedy is the starting point.

Python Greedy versus optimal knapsack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Nearest neighbor for the TSP

For the traveling salesman problem, the greedy construction is the nearest-neighbor rule: start at a city and repeatedly go to the closest unvisited city, finally returning home. It is simple, fast (about nยฒ steps) and usually 15 to 25 percent above the optimum on random maps. Its weakness is the end: after the early greedy choices, the last unvisited cities may be scattered far apart, forcing long edges, and the return trip may be long.

2-opt: improving a tour by uncrossing edges

Local search takes any tour and tries small modifications. The classic move for tours is 2-opt: pick two edges (a, b) and (c, d), delete them and reconnect as (a, c) and (b, d), which reverses the segment between b and c. If the new tour is shorter, keep it. Whenever a tour crosses itself, 2-opt can shorten it (by the triangle inequality, an uncrossing never lengthens the tour in the plane).

The process stops when no 2-opt move helps: the tour is a 2-opt local optimum. It is usually within about 5 percent of optimal.

Python Nearest neighbor and 2-opt on twelve cities

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The numbers show the whole story of this chapter in miniature: a 21 percent gap after the greedy build, and about 1.5 percent after local search, in a few milliseconds. Notice that the final tour is still not the optimum (345.78): it is a local optimum, a tour that no single 2-opt move can improve.

Different starts, different local optima

The result of local search depends on where you start. A simple and powerful trick is multi-start: run the heuristic from many different starting tours and keep the best. The next program starts 2-opt from random tours.

Python Multi-start 2-opt

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Multi-start reveals the typical spread of local optima. Keeping the best of many starts usually finds a tour very close to the optimum for small maps.

How to judge a heuristic

  1. Compare with a known optimum or bound on small instances (as we did with Held-Karp). A gap of a few percent is typical for good local search.
  2. Compare with simple baselines: random tours, the current manual plan, or the previous system.
  3. Check running time as the instance grows. Nearest neighbor grows like nยฒ; a full 2-opt pass also grows like nยฒ, and several passes may be needed.
  4. Test robustness: different random seeds and different data. A method that wins on one map and loses on others is not reliable.

Other construction ideas

Different problems call for different greedy rules.

  • Insertion heuristics for tours: start with a small loop and repeatedly insert the city whose addition increases the length the least. They often beat nearest neighbor.
  • The savings algorithm (Clarke and Wright, 1964) for vehicle routing: start with one route per customer and merge routes in the order of the largest saving in distance. It is still a standard baseline in logistics.
  • First-fit decreasing for bin packing: sort items from large to small and put each in the first bin where it fits. It is simple, fast and guaranteed to use at most about 11/9 of the optimal number of bins plus a small constant.
  • Earliest due date and shortest processing time for scheduling are also greedy rules, with proofs for special objectives, as you saw in chapter 5.

Other neighborhoods

For tours, besides 2-opt there are or-opt moves (move a short chain of cities to another place) and 3-opt moves (reconnect three edges), which explore more but cost more per pass. For scheduling, neighborhoods swap two jobs or insert a job at another position. For knapsack-type problems, neighbors add, remove or swap one item. A larger neighborhood means fewer local optima and better solutions, but each step costs more, so practitioners balance the two. A classic variant, the Lin-Kernighan method, builds long chains of moves adaptively and is among the best practical TSP heuristics.

Common misconceptions

"Greedy means optimal." Greedy is optimal only for special problems (for example, the fractional knapsack where items can be split, or minimum spanning trees). Otherwise it can be far from the best.

"Local search finds the global optimum if I run it long enough." It stops at the first local optimum. Longer runs help only if you restart or allow worse moves (the next lesson).

"A heuristic's gap is known." You know the gap only when you have an optimum or a bound. Otherwise report the best value you found, not a claimed gap.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In the knapsack lesson, why did the greedy ratio rule fail?

    Taking Q used up weight that P and R together could use better; greedy rules never reconsider.
  2. 2. What does a 2-opt move do?

    It replaces edges (a, b) and (c, d) by (a, c) and (b, d), reversing the path between them.
  3. 3. A tour of length 360 is found when the optimum is 345.8. What is the gap, to the nearest percent?

    (360 โˆ’ 345.8)/345.8 โ‰ˆ 0.041, about 4%.
  4. 4. What is the purpose of multi-start local search?

    Different starts lead to different local optima; the best of them is usually better than a single run.
  5. 5. The nearest-neighbor rule is an example of...

    It builds a tour by always taking the closest unvisited city, which is a greedy construction.

Summary

  • Greedy construction builds a solution quickly but never reconsiders; it can be far from optimal.
  • Local search improves a solution with small moves (such as 2-opt) until none helps, reaching a local optimum.
  • Multi-start search runs local search from many starts and keeps the best.
  • Judge heuristics by their gap to a known optimum or bound, their speed and their robustness.

Next: Simulated annealing