Skip to content
Tutorials Center
My learning

Topics

Lesson 39 of 49 ยท Heuristics and Practice

Chapter 8 Overview: Heuristics and Practice

A map of chapter 8: why some optimization problems defeat exact methods, how heuristics find good answers fast, and how operations research projects work in practice.

Linear programs can have millions of variables and still be solved in minutes. Yet a delivery planner choosing the order of stops for a single truck with a few dozen customers can run into a problem that no known method solves exactly in reasonable time. The difference is not the size of the data; it is the structure of the problem. This chapter is about what to do when exact methods are too slow: use a heuristic, a method that finds a good solution quickly without promising that it is the best.

It also closes the loop with practice. Methods matter only if they end up changing decisions, so the last lesson of the chapter follows the whole workflow of a real project.

A landscape where an uphill search gets stuck on a small hill
Caption: A search that only ever goes uphill stops at the nearest peak; heuristics aim to get close to the best peak quickly, and metaheuristics add ways to escape.

What you will learn

  • Why some problems explode in difficulty and what "NP-hard" means in practice.
  • The difference between exact methods, heuristics and metaheuristics.
  • How to measure a heuristic's quality with an optimality gap.
  • How the chapter's lessons fit together.

Key terms

Heuristic: a practical rule or procedure that finds a good solution quickly but gives no guarantee of optimality.

Local optimum: a solution that no small change can improve, though a better one may exist elsewhere.

Metaheuristic: a general strategy (simulated annealing, genetic algorithms, tabu search) for guiding heuristics to avoid getting stuck.

NP-hard: a problem class for which no fast exact algorithm is known; exact solution times grow explosively with size.

Optimality gap: (heuristic value โˆ’ best value) / best value, the percentage by which a heuristic misses the best answer.

When exact methods run out of steam

Take the traveling salesman problem (TSP): visit every city once and return home, minimizing the distance. For n cities, the number of distinct round trips is (n โˆ’ 1)! / 2:

Cities Number of tours
5 12
10 181,440
12 19,958,400
20 about 6 ร— 10ยนโถ
30 about 4 ร— 10ยณโฐ

A computer checking a billion tours per second would need over a year to finish 20 cities and far longer than the age of the universe for 30. Clever exact algorithms (branch and bound, dynamic programming, cutting planes) push the limit a long way (modern solvers handle thousands of cities), but they still take hours or days, and the general problem is NP-hard. Many other practical problems share this behavior: vehicle routing, scheduling many machines, bin packing, timetabling, facility layouts.

Three families of methods

Exact methods

Guarantee Provably the best
Cost Time can explode
1 / 4

An important rule of thumb: when a good heuristic exists, a solution a few percent from optimal is usually worth far more than a perfect answer delivered too late. A route that is 3 percent longer than optimal but ready in a second is better than the best route computed after the trucks have left.

Counting tours and finding the exact answer

The first program shows how fast the count grows. The second finds the true optimum for 12 cities with a clever dynamic program (the Held-Karp algorithm, which needs about nยฒ ยท 2โฟ steps instead of n!) and compares it with a quick heuristic.

Python How fast tours multiply

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.

Python Exact optimum for 12 cities by dynamic programming

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.

Exact dynamic programming is fine for 12 cities but hopeless for 40, since 2โดโฐ states is about a trillion. Heuristics keep working. The next lessons build them.

Where the chapter goes

Lesson What you will learn
Construction heuristics and local search Greedy rules, nearest neighbor, knapsack by ratio, 2-opt moves and local optima
Simulated annealing Accepting worse moves, cooling schedules, and a run on the TSP; tabu and genetic ideas
From messy problem to decision The OR workflow, modelling a small business problem, sensitivity analysis and validation
Chapter 8 review A recap picture and a ten-question quiz

For evolutionary methods in depth, see the genetic algorithms track.

Common misconceptions

"A heuristic is a bad solution." A well-chosen heuristic is often within a few percent of optimal; the real cost is that you do not know how close.

"Exact methods are always better." If they cannot finish in time, they deliver nothing. Many practical systems run a heuristic for speed and an exact method as an offline check.

"Big problems need big computers." Often they need a better formulation or a smarter algorithm.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many distinct round trips visit 6 cities once each? Use (n โˆ’ 1)!/2.

    (6 โˆ’ 1)!/2 = 120/2 = 60.
  2. 2. What is a local optimum?

    Local search stops at such a solution even when a better one exists elsewhere.
  3. 3. A heuristic gives a tour of length 105 while the optimum is 100. What is the optimality gap?

    (105 โˆ’ 100)/100 = 5%.
  4. 4. Which is NOT a metaheuristic?

    Simulated annealing and genetic algorithms are metaheuristics; dividing by zero is simply an error.

Summary

  • Some problems (TSP, vehicle routing, large scheduling) are NP-hard: exact solution times explode.
  • Heuristics deliver good answers fast without a guarantee; metaheuristics help escape local optima.
  • The optimality gap measures how far a heuristic is from the best known answer.
  • A fast good answer usually beats a late perfect one.

Next: Construction heuristics and local search