Full index¶
How to use these notes¶
- Website and PDF. Each chapter of the website is a chapter of the lecture notes, with the same numbers and the same colors; long chapters are split into one page per section.
- At the top of each chapter a bar with the PDF of the lecture notes, the slides, the exercises and the apps of the chapter; at the bottom, the link to the exercises.
- The problems. Definitions, instances and formulations of the problems are in the course Combinatorial Optimization Problems: the chapters link to them.
- The code. On the pages the algorithms are in pseudo-code; the «Run in Colab» buttons open the notebook with the code in Python and C++.
The boxes have the same colors as in the lecture notes:
Definition
The precise meaning of a new concept.
Theorem, proposition, observation
A result to remember, with its hypotheses.
Example
A computation worked out in full, one step at a time.
Formula
In pink the formulas to keep at hand.
Algorithm
The pseudo-code, step by step as in the lecture notes.
In green the key point to take away.
Proof: opens with a click
All proofs are included, but folded: first read the statement, then open the proof when you want to study it. The same holds for the solutions of the exercises.
All the pages of the website, in the order of the menu: the chapters with their sections and the other pages.
Heuristic Algorithms¶
- 1. Heuristic algorithms: definitions · Exercises
- 1.1 Heuristic algorithms
- 1.2 The problems and the assumptions
- 1.3 Primal and dual bounds
- 1.4 Classification of heuristic algorithms
- 1.5 Solution representation and search space
- 1.6 Neighbourhoods and local optima
- 1.7 Intensification and diversification
- 1.8 How to evaluate a heuristic algorithm
- 1.9 Typical mistakes
- 1.10 In summary
- 2. Constructive heuristics · Exercises
- 2.1 Constructive heuristics
- 2.2 The problems and the assumptions
- 2.3 The greedy paradigm
- 2.4 The 0/1 knapsack problem: which order?
- 2.5 The bin packing problem: first sort, then pack
- 2.6 Scheduling on parallel machines: longest jobs first
- 2.7 The travelling salesman problem: append or insert?
- 2.8 Vertex coloring: greedy and DSATUR
- 2.9 Randomized construction
- 2.10 Look-ahead and regret
- 2.11 What constructive heuristics give, and what they do not
- 2.12 Typical mistakes
- 2.13 In summary
- 3. Local search · Exercises
- 3.1 Local search
- 3.2 The problems, the assumptions and the starting solutions
- 3.3 Local search: the scheme
- 3.4 Neighbourhoods for the four problems
- 3.5 First improvement and best improvement
- 3.6 Evaluating a move incrementally
- 3.7 TSP: 2-opt and Or-opt
- 3.8 \(P\,||\,C_{\max}\): move and swap
- 3.9 Flat landscapes and auxiliary objectives
- 3.10 KP: feasibility and penalties
- 3.11 Variable neighbourhood descent
- 3.12 Multi-start local search
- 3.13 Typical mistakes
- 3.14 In summary
- 4. Metaheuristics · Exercises
- 4.1 Metaheuristics
- 4.2 The problems and the assumptions
- 4.3 How to escape from a local optimum
- 4.4 Simulated annealing
- 4.5 Tabu search
- 4.6 Iterated local search
- 4.7 Variable neighbourhood search
- 4.8 GRASP
- 4.9 Large neighbourhood search
- 4.10 Population-based methods: genetic and memetic algorithms
- 4.11 Comparison and conclusions
- 4.12 Typical mistakes
- 4.13 In summary
- 5. MIP heuristics for the classical problems · Exercises
- 5.1 MIP-based heuristics
- 5.2 The problems and their MIP models
- 5.3 Rounding
- 5.4 Diving
- 5.5 The feasibility pump
- 5.6 RINS, local branching and proximity search
- 5.7 Relax-and-fix and fix-and-optimize on lot sizing
- 5.8 Heuristics inside the solver
- 5.9 What the MIP-based heuristics give
- 5.10 Typical mistakes
- 5.11 In summary