Skip to content
Tutorials Center
My learning

Topics

Lesson 43 of 49 ยท Heuristics and Practice

Chapter 8 Review: Heuristics and Practice

Review chapter 8 with a one-page picture, a table of heuristic families, a gap calculator and a ten-question quiz on greedy rules, 2-opt, annealing and the OR workflow.

This chapter began with a puzzle: why can a tiny routing problem defeat the methods that solve giant linear programs? The answer was NP-hardness, and the response was a family of practical methods: greedy construction, local search, and metaheuristics such as simulated annealing. Then you saw the other half of the job, the workflow that turns a model into a decision.

Four cards: constructive heuristics, local search, simulated annealing and practice
Caption: The chapter on one page: build, improve, escape and then communicate.

What you will learn

  • To choose between constructive, local-search and metaheuristic approaches.
  • To compute and interpret optimality gaps and annealing probabilities.
  • To recall the steps and checks of an OR project.

The recap table

Idea What it does Strength Weakness
Greedy / nearest neighbor Builds a solution step by step Very fast, simple Never reconsiders; can be 20% or more off
Local search (2-opt, swaps) Improves a solution by small moves Big gains cheaply Stops at a local optimum
Multi-start Repeats local search from many starts Easy to parallelize Many runs needed
Simulated annealing Accepts worse moves with exp(โˆ’ฮ”/T) Escapes local optima Needs a cooling schedule, no guarantee
Tabu / genetic / ant colony Memory, populations, pheromone Flexible Tuning effort
Exact methods Prove optimality Guarantee Time can explode
OR workflow Understand, model, solve, validate, deploy Produces decisions Requires people and iteration

Two small calculators

The first computes optimality gaps and the Metropolis acceptance probability; the second reproduces the budgeting idea behind a cooling schedule.

Python Gaps, acceptance probabilities and cooling steps

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.

Two mixed worked problems

Problem A. A route-planning heuristic returns a route of 1,260 km; the best known route is 1,200 km. The gap is 100 ร— 60/1,200 = 5%. A second heuristic returns 1,236 km in the same time. Its gap is 3 percent, so it is the better method at equal running time.

Problem B. Simulated annealing starts at T0 = 50 and cools with ฮฑ = 0.98 per step. How many steps until T = 1? ln(1/50) / ln(0.98) = (โˆ’3.912)/(โˆ’0.0202) โ‰ˆ 194 steps. At T = 4, the probability of accepting a move that is 8 units worse is e^{โˆ’2} โ‰ˆ 0.135; at T = 1 it is e^{โˆ’8} โ‰ˆ 0.0003.

Problem C. Why can a greedy knapsack by value per kilogram be suboptimal? Because it never reconsiders: in the example of the construction lesson it fills the bag with items P and Q (value 182), while P and R (value 202) fit better. Local search could fix this by trying to swap one item for another.

Putting the chapter together

A typical project uses everything in this chapter. First, define the real question (workflow step 1). Then choose a model and, if it is hard, a heuristic: construct a starting solution greedily, improve it with local search, add annealing or restarts if the results vary. Finally, measure the gap against a bound or a small instance solved exactly, and present the result with its sensitivity. The recipe "construct, improve, escape, validate" works for routing, scheduling, packing and timetabling alike.

A self-test before the quiz

Close the page and try to answer these aloud. What is the difference between a heuristic and a metaheuristic? Why does greedy construction often end far from the optimum? What does a 2-opt move do to a tour? Why does annealing keep a separate record of the best solution? How would you pick a starting temperature? What are the five steps of the workflow, and which one do people most often skip? If you hesitate on any of them, reread the matching lesson before taking the quiz, because the quiz mixes all four lessons of the chapter.

Common misconceptions

"A bigger gap means a worse method." Compare methods at equal running time. A method with a 2 percent gap that takes a day can be less useful than one with 5 percent in a second.

"Heuristics do not need testing." They need more testing, across many instances and seeds, because they carry no proof.

Check your understanding

Quick check ยท 10 questions

of 10 answered You scored / 10 ยท perfect!

  1. 1. Greedy construction means...

    Greedy methods commit to the locally best choice at every step.
  2. 2. A tour has length 110 and the best known is 100. The gap is...

    (110 โˆ’ 100)/100 = 10%.
  3. 3. A 2-opt move on a tour...

    The segment between the removed edges is reversed to form a new tour.
  4. 4. A local optimum is...

    Better solutions may exist, but not within one move.
  5. 5. A worse move with ฮ” = 4 at T = 2 is accepted with probability...

    exp(โˆ’ฮ”/T) = exp(โˆ’4/2) = exp(โˆ’2) โ‰ˆ 0.135.
  6. 6. As T falls toward 0 in simulated annealing, the method behaves like...

    Worse moves are almost never accepted, so only improvements remain.
  7. 7. Which is the right order of the OR workflow?

    Start with the problem, build and solve a model, check it, then put it to use, iterating as needed.
  8. 8. A shadow price of 0 for a resource means...

    If a constraint has slack, extra capacity brings no gain.
  9. 9. Why record the best solution found in simulated annealing?

    Worse moves are allowed, so the last solution is not necessarily the best.
  10. 10. Why is a fast, 3 percent-gap heuristic often preferable to a slow exact method?

    A good answer in time beats a perfect answer too late.

Summary

  • Construct quickly, improve with local search, escape with metaheuristics, and measure the gap whenever you can.
  • Annealing accepts a worse move with probability exp(โˆ’ฮ”/T) and cools gradually.
  • An OR project is a loop of understanding, modelling, solving, validating and deploying.
  • Chapter 9 puts everything into two projects and a practice set.

Next: Chapter 9: Project, an inventory policy by simulation