Network Optimization¶

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

The course lecture notes, online: graphs, minimum spanning trees, shortest paths, network flows (maximum flow, minimum cost flow, transportation and assignment), the network simplex and project management; with definitions, results with proofs, examples worked out step by step and exercises with solutions.

For third-year students of the Bachelor's degree in Management Engineering at Sapienza, and for anyone who wants to learn network optimization. Prerequisites: Linear Programming.

Study the course 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.

Graphs

Part 1 · Chapter 1

Graphs

The part
Trees and paths

Part 2 · Chapters 2–3

Spanning trees · Shortest paths

The part
Flows

Part 3 · Chapters 4–7

Flow models · Maximum flow · Minimum cost flow · Transportation and assignment

The part
The network simplex

Part 4 · Chapter 8

Network simplex

The part
Project management

Part 5 · Chapter 9

Project management

The part
Lab

Interactive apps

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

The apps

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 part, the PDF of the volume and the exercises of the chapter; at the bottom, the link to the exercises.

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.

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;
Combinatorial Optimization — knapsack, bin packing, coloring, TSP, scheduling and lot sizing, solved in every way;
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.

Questo sito è disponibile anche in italiano.