Full index¶
All the pages of the website, in the order of the menu: the chapters with their sections, the catalogue and the other pages.
Combinatorial optimization¶
Selected problems¶
- 2. Knapsack problems · Exercises
- 2.1 Overview of the family
- 2.2 The 0/1 knapsack problem
- 2.3 The subset sum problem
- 2.4 The bounded knapsack problem
- 2.5 The unbounded knapsack problem
- 2.6 The multidimensional knapsack problem
- 2.7 The multiple knapsack problem
- 2.8 The multiple-choice knapsack problem
- 2.9 The knapsack problem with setups
- 2.10 Remarks
- 2.11 Typical mistakes
- 2.12 In summary
- 3. Packing problems · Exercises
- 4. Coloring problems · Exercises
- 5. Clique problems · Exercises
- 6. Routing problems · Exercises
- 7. Scheduling problems · Exercises
- 8. Lot sizing problems · Exercises
Formulations¶
- 9. Formulations of knapsack problems · Exercises
- 9.1 Overview of the family
- 9.2 An ILP model for the 0/1 Knapsack Problem
- 9.3 A first Linear Programming relaxation
- 9.4 A second Linear Programming relaxation
- 9.5 0/1 Knapsack Problem upper bounds
- 9.6 An ILP model for the Subset Sum Problem
- 9.7 An ILP model for the Bounded Knapsack Problem
- 9.8 An ILP model for the Unbounded Knapsack Problem
- 9.9 An ILP model for the Multidimensional Knapsack Problem
- 9.10 An ILP model for the Multiple Knapsack Problem
- 9.11 An ILP model for the Multiple-Choice Knapsack Problem
- 9.12 An ILP model for the Knapsack Problem with Setups
- 9.13 Typical mistakes
- 9.14 In summary
- 10. Formulations of packing problems · Exercises
- 11. Formulations of coloring problems · Exercises
- 12. Formulations of clique problems · Exercises
- 12.1 Overview of the family
- 12.2 An ILP model for the Maximum Clique Problem: the edge formulation
- 12.3 A first Linear Programming relaxation
- 12.4 A second Linear Programming relaxation
- 12.5 Clique inequalities: a stronger formulation
- 12.6 The relation with vertex coloring
- 12.7 Stable sets on the complement graph
- 12.8 ILP models for the weighted variants
- 12.9 Typical mistakes
- 12.10 In summary
- 13. Formulations of routing problems · Exercises
- 13.1 Overview of the family
- 13.2 ILP models for the Travelling Salesman Problem
- 13.3 A model with position variables (MTZ)
- 13.4 A model with subtour elimination constraints (DFJ)
- 13.5 Linear Programming relaxations
- 13.6 ILP models for the metric and asymmetric TSP
- 13.7 Typical mistakes
- 13.8 In summary
- 14. Formulations of scheduling problems · Exercises
- 15. Formulations of lot sizing problems · Exercises
- 15.1 Overview of the family
- 15.2 ILP models for the Capacitated Lot Sizing Problem
- 15.3 A formulation with a big-M link
- 15.4 The Linear Programming relaxation of the big-M formulation
- 15.5 A shortest-path formulation
- 15.6 Comparing the formulations
- 15.7 ILP models for the variants
- 15.8 Typical mistakes
- 15.9 In summary
Dynamic programming¶
Knapsack problems¶
- 17. DP for the 0/1 knapsack problem · Exercises
- 18. DP for the unbounded knapsack problem · Exercises
- 19. DP for the bounded knapsack problem · Exercises
- 20. DP for the subset sum problem · Exercises
- 21. DP for the multiple-choice knapsack problem · Exercises
- 22. DP for the multidimensional knapsack problem · Exercises
- 23. DP for the knapsack problem with setups · Exercises
- 24. DP for the multiple knapsack problem · Exercises
Lot sizing problems¶
- 25. DP for the uncapacitated lot sizing problem · Exercises
- 26. DP for the capacitated lot sizing problem · Exercises
Miscellaneous problems¶
Heuristics¶
- 29. Heuristic algorithms: definitions · Exercises
- 29.1 Heuristic algorithms
- 29.2 The problems and the assumptions
- 29.3 Primal and dual bounds
- 29.4 Classification of heuristic algorithms
- 29.5 Solution representation and search space
- 29.6 Neighbourhoods and local optima
- 29.7 Intensification and diversification
- 29.8 How to evaluate a heuristic algorithm
- 29.9 Typical mistakes
- 29.10 In summary
- 30. Constructive heuristics · Exercises
- 30.1 Constructive heuristics
- 30.2 The problems and the assumptions
- 30.3 The greedy paradigm
- 30.4 The 0/1 knapsack problem: which order?
- 30.5 The bin packing problem: first sort, then pack
- 30.6 Scheduling on parallel machines: longest jobs first
- 30.7 The travelling salesman problem: append or insert?
- 30.8 Vertex coloring: greedy and DSATUR
- 30.9 Randomized construction
- 30.10 Look-ahead and regret
- 30.11 What constructive heuristics give, and what they do not
- 30.12 Typical mistakes
- 30.13 In summary
- 31. Local search · Exercises
- 31.1 Local search
- 31.2 The problems, the assumptions and the starting solutions
- 31.3 Local search: the scheme
- 31.4 Neighbourhoods for the four problems
- 31.5 First improvement and best improvement
- 31.6 Evaluating a move incrementally
- 31.7 TSP: 2-opt and Or-opt
- 31.8 \(P\,||\,C_{\max}\): move and swap
- 31.9 Flat landscapes and auxiliary objectives
- 31.10 KP: feasibility and penalties
- 31.11 Variable neighbourhood descent
- 31.12 Multi-start local search
- 31.13 Typical mistakes
- 31.14 In summary
- 32. Metaheuristics · Exercises
- 32.1 Metaheuristics
- 32.2 The problems and the assumptions
- 32.3 How to escape from a local optimum
- 32.4 Simulated annealing
- 32.5 Tabu search
- 32.6 Iterated local search
- 32.7 Variable neighbourhood search
- 32.8 GRASP
- 32.9 Large neighbourhood search
- 32.10 Population-based methods: genetic and memetic algorithms
- 32.11 Comparison and conclusions
- 32.12 Typical mistakes
- 32.13 In summary
- 33. MIP heuristics for the classical problems · Exercises
- 33.1 MIP-based heuristics
- 33.2 The problems and their MIP models
- 33.3 Rounding
- 33.4 Diving
- 33.5 The feasibility pump
- 33.6 RINS, local branching and proximity search
- 33.7 Relax-and-fix and fix-and-optimize on lot sizing
- 33.8 Heuristics inside the solver
- 33.9 What the MIP-based heuristics give
- 33.10 Typical mistakes
- 33.11 In summary
Approximation¶
Knapsack problems¶
- 35. Approximation algorithms for the knapsack problem · Exercises
- 35.1 Notation
- 35.2 Split item and residual capacity
- 35.3 The greedy algorithm
- 35.4 The Ext-Greedy algorithm
- 35.5 The \(H^2\) algorithm
- 35.6 The \(H^{\ell}\) algorithm
- 35.7 The Basic-FPTAS algorithm
- 35.8 Performance guarantees
- 35.9 Absolute performance guarantee
- 35.10 Typical mistakes
- 35.11 In summary
Packing problems¶
Coloring problems¶
Clique problems¶
Routing problems¶
Scheduling problems¶
Ad hoc algorithms¶
Knapsack problems¶
Coloring problems¶
Catalogue¶
- The problems at a glance
- Knapsack problems: 0/1 knapsack (KP) · Subset sum (SSP) · Bounded knapsack (BKP) · Unbounded knapsack (UKP) · Multidimensional knapsack (MDKP) · Multiple knapsack (MKP) · Multiple-choice knapsack (MCKP) · Knapsack with setups (KPS)
- Packing problems: Bin packing (BPP) · Cutting stock (CSP)
- Coloring problems: Vertex coloring (VCP)
- Clique problems: Maximum clique (MCP) · Maximum stable set (MSSP) · Vertex-weighted maximum clique (VWMCP) · Edge-weighted maximum clique (EWMCP)
- Routing problems: Travelling salesman (TSP) · Metric TSP · Asymmetric TSP (ATSP) · Hamiltonian cycle (HCP)
- Scheduling problems: Identical parallel machines (P||Cmax) · Fixed number of identical machines (Pm||Cmax) · Parallel machines with different speeds (Q||Cmax) · Unrelated parallel machines (R||Cmax)
- Lot sizing problems: Capacitated lot sizing (CLS) · Uncapacitated lot sizing (ULS) · Capacitated lot sizing with constant capacity (CLS-C) · Lot sizing with several products and setup times (MLS) · Lot sizing with initial stock (LS-SI) · Lot sizing with overtime (LS-OT) · Lot sizing with unsatisfied demand (LS-UD)
- Miscellaneous problems: Rod cutting (RCP) · Coin change (CCP)