Interactive lab¶
Here you can get your hands on heuristic algorithms: each app runs an algorithm step by step on the reference instances of the course, which you can also change. Pick an app: it opens full page. Everything runs in the browser; the numbers are computed by the algorithm, not typed by hand.
Chapter 2 · Constructive heuristics¶
-
Bin packing heuristics
Next Fit, First Fit, Best Fit, Worst Fit and FFD step by step, with the bound and the optimum. In «You pack» you try to beat the algorithm.
-
List scheduling and LPT
The Gantt chart is built job by job; next to it the bound max{max t_j, ⌈Σ t_j / m⌉} and the optimum.
-
Vertex coloring: greedy and DSATUR
The graph is colored vertex by vertex with greedy and DSATUR: Petersen, crown graph or a random graph.
Chapter 3 · Local search¶
-
TSP: nearest neighbour and 2-opt
The tour is built city by city and then 2-opt improves it: on the course instance or in the plane, with cities to drag.
Chapter 4 · Metaheuristics¶
-
TSP: simulated annealing and tabu search
The two metaheuristics with 2-opt, on the reference instance, on TSP20 and on the instance of the exercises, with the random numbers of the notes: current tour, best tour and length curve.