optional · interactive figures
19
Explore: search, restarts and LNS
Luby's restart schedule as a growing bar chart, and LNS improving a job-shop one destroy-and-repair step at a time.
optional: nothing in the lab depends on it back to the slides
These figures support the slides; they don't replace them, and the unit is complete
without them. Each one is computed from the unit's own data or reference solution, so
what you see agrees with the numbers on the slides.
Inside a figure, the arrow keys and drags belong to the figure; click outside it (or
press Esc) to use them for the slides again.
19 · explore
Luby cutoffs, as bars
Try: slide the number of runs to 15, 31 and 63, and read the effort table: every cutoff size gets the same total. Static version: Luby cutoffs, term by term .
What it shows. The restart cutoffs luby(i) × base for the first runs, and how much
total effort each cutoff size receives. After 2k − 1 runs every size has been given the
same effort, which is what makes the schedule universal.
Data. The reference luby(i) for i = 1..127, recorded by
slides/viz/traces/u19.py; the base only multiplies.
19 · explore
Destroy and repair, iteration by iteration
Try: the deck's 3 × 3 shop improves 16 → 12 in one step; the 6 × 4 shop falls from 57 to 39 over ten, with some steps that find nothing. Static version: One LNS step .
What it shows. Large neighbourhood search on a job-shop. Each step frees some jobs
(bright), keeps the other jobs' order on every machine (faded), and asks the solver for a
schedule with a smaller makespan. The line below tracks the incumbent.
Data. slides/viz/traces/u19.py replays the reference
lns_jobshop loop with the same random choices, unit 18's model and unit 17's
solve, and checks that each run ends at the reference function's result.