Biological meta-heuristics:
Genetic algorithm, ant colony algorithms.

Linear programming for discrete optimisation:
The formulation of linear programming problem. Simplex algorithm (local search on the vertices of a polyhedron). Peculiarities of integer linear programming.

Rounding:
Rounding solutions of linear programs to get solutions of combinatorial problems. Simple rounding for vertex cover problem. Randomized rounding. Balancing trade-offs in knapsack via rounding.

Duality:
Duality in linear programming. Max flow and shortes path as dual problems. Using duality to obtain an LP-free algorithm for weighted vertex cover.

Reoptimisation:
Reoptimisation illustrated on the travelling salesman problem.

Discrete linear subset (DLS) problem:
TSP and MST as special cases of DLS. Matroids as data structures with efficient greedy solution of DLS problems.

Branch-and-bound techniques:
A* search. Branch-and-bound for TSP; the Held–Karp bound.

Online optimisation:
Online optimisation illustrated on bin packing and scheduling.

Tree problems:
Recap of minimum spanning tree (MST) problem. Steiner tree problem; application of metric closure.

Heuristics directly based on local search:
Simulated annealing and tabu search.

Local search algorithms:
Pros and cons. Kernigan–Lin modification of local search (KL-heuristic).

Classical problems in discrete optimisation:
Problems on graphs and networks, cover problems, bin packing, knapsack, scheduling. Quality metrics for approximate algorithms.

Flow problems:
Recap of maximal flow algorithms. Min-cost flow algorithms.

Final recap