Integer Linear Programming¶
Teaching material by Fabio Furini, associate professor at DIAG, Sapienza University of Rome.
The course covers integer and mixed integer programming models, LP relaxations, ideal formulations, valid inequalities, cutting planes, branch-and-bound, branch-and-cut, MIP solvers and heuristics. It includes definitions, proofs, worked examples and exercises with solutions.
Start with the chapters Go to the exercises Open the interactive lab Download materials
How each chapter is organized¶
Each chapter is one of the course notes, with the same numbers and the same colors as the lecture notes: on the website and in the PDF you find everything in the same place.
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.
In green the key point to take away.
Algorithm
The pseudocode of a method, in red.
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.
The parts of the course¶
-
I · Models and bounds
What an integer linear programming problem is (MIP, ILP, BIP), its solutions and outcomes; primal and dual bounds, the gap and the LP relaxation.
1. Integer linear programming · 2. Primal and dual bounds
-
II · Strengthening the formulation
Ideal formulations, valid inequalities and cover inequalities: how to strengthen a formulation.
3. Ideal formulations · 4. Valid inequalities · 5. Cover inequalities
-
III · Exact methods
The cutting plane algorithm with Gomory fractional cuts, LP-based branch-and-bound and branch-and-cut. Examples worked out step by step and exercises with complete solutions.
6. The cutting plane algorithm with Gomory fractional cuts · 7. LP-based branch-and-bound · 8. Branch-and-cut
-
IV · MIP solvers
What a MIP solver does (presolve, cuts, primal heuristics, tree strategies, tolerances) and how to read its log, with real examples.
9. MIP solvers: what they do
-
V · MIP heuristics
Rounding, diving, feasibility pump, RINS, local branching, relax-and-fix and fix-and-optimize. Examples and exercises with complete solutions.
10. MIP heuristics
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;
- Combinatorial Optimization — knapsack, bin packing, coloring, TSP, scheduling and lot sizing, solved in every way;
- 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.