Skip to content

Combinatorial Optimization

Teaching material conceived and developed by Fabio Furini, associate professor at DIAG, Sapienza University of Rome.

The course lecture notes, online: knapsack, packing, coloring, clique, routing, scheduling and lot sizing problems, studied through formulations and their properties, dynamic programming, heuristic, approximation and ad hoc algorithms; with definitions, results with proofs, examples worked out step by step, exercises with solutions, Colab notebooks and interactive apps.

For the students of the Master's degree in Management Engineering at Sapienza, and for anyone who wants to learn how to solve combinatorial optimization problems. Prerequisites: Integer Linear Programming for the formulations and Algorithms for the algorithms.

Study the course Explore the problems Practice Get the materials

The parts of the course

The same entries as the menu: each card gives its part and its chapters in the lecture notes.

  • Combinatorial optimization

    Part 1 · Chapter 1

    What a combinatorial optimization problem is: categories, counting the solutions, combinatorial explosion, bounds and gap, complexity.

    The chapter

  • Selected problems

    Part 1 · Chapters 2–8

    Knapsack problems · Packing problems · Coloring problems · Clique problems · Routing problems · Scheduling problems · Lot sizing problems

    The families

  • Formulations

    Part 2 · Chapters 9–15

    Knapsack problems · Packing problems · Coloring problems · Clique problems · Routing problems · Scheduling problems · Lot sizing problems

    The chapters

  • Dynamic programming

    Part 3 · Chapters 16–28

    Principles · Knapsack problems · Lot sizing problems · Miscellaneous problems

    The chapters

  • Heuristics

    Part 4 · Chapters 29–33

    Definitions · Constructive heuristics · Local search · Metaheuristics · MIP heuristics

    The chapters

  • Approximation

    Part 5 · Chapters 34–40

    Principles · Knapsack problems · Packing problems · Coloring problems · Clique problems · Routing problems · Scheduling problems

    The chapters

  • Ad hoc algorithms

    Part 6 · Chapters 41–42

    Knapsack problems · Coloring problems

    The chapters

  • Catalogue

    All the problems

    One page per problem, by family: definition, assumptions and what the course does on the problem.

    The catalogue · PDF

  • Lab

    Interactive apps

    The algorithms of the course step by step, on the reference instances or on your own.

    The apps

  • Colab notebooks

    Python · C++

    The code of the algorithms of the chapters, to run in Google Colab on the examples and the exercises.

    The notebooks

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 or per problem.
  • At the top of each chapter a bar with the part, the PDF of the volume, the exercises and the apps of the chapter; at the bottom, the link to the exercises.
  • By problem. The catalogue has one page per problem: its definition and the chapters that treat it, technique by technique.
  • 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 (for example the recurrences of dynamic programming).

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.

By the same author:

  • Linear Programming — polyhedra, the simplex algorithm, duality and the dual simplex, with the interactive lab;
  • Convex Optimization — convex sets and functions, convex optimization problems, with interactive graphs;
  • Algorithms — number representation, pseudo-code, sorting and searching, analysis and recursive algorithms;
  • Integer Linear Programming — LP relaxation, valid inequalities, cutting planes, branch-and-bound and branch-and-cut;
  • Network Optimization — graphs, spanning trees, shortest paths, network flows, the network simplex and project management;
  • MIP Modelling — integer linear programming models, from the formulation to the solution with solvers;
  • Operations Research Lab — modelling and solving optimization problems with Python and solvers;
  • Mathematical Analysis 1 — real numbers, functions, limits, derivatives and series, with interactive graphs;
  • Linear Algebra — vectors, matrices, determinants, linear systems and eigenvalues, with the computation lab.

Teaching material by Fabio Furini — DIAG, Sapienza University of Rome.

This website is also available in Italian.