00884 - Operation Research

Learning outcomes

At the end of the course, the student knows the main models and algorithms for linear and integer programming and graph theory.

Course contents

1. Mathematical models of optimization problems
Definition of a mathematical model, decision variables, objective function and requirements or constraints. Mathematical modeling techniques.
Examples of mathematical models for real-world applications.

2. Continuous Linear Programming (PLC) and Integer Programming (PLI).

Mathematical models with continuous variables. Geometric resolution. PLC theory and simplex algorithm
Mathematical models with integer variables. Geometric interpretation. Properties of PLI problems. Relaxation techniques. Cutting-plane algorithms (CP). Branch-and-bound method (B&B). Applications of the B&B technique.

3. Elements of graph theory and its main problems.

Main definitions of graph theory. Minimum cost spanning trees (SST). Minimal paths (CM). Network flow problems (FR), maximum flow, minimum cost flow. Linear assignment.

Readings/Bibliography

Lecture notes and slides by teacher available online

Texts for consultation only:

• Matteo Fischetti, Operations Research Lessons, Project Library.
• C. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, NY.
• R.K.Ahuja, T.L.Magnanti, J.B.Orlin, "Network flows: theory, algorithms and applications", Prentice Hall.
• M. Gondran, M. Minoux, "Graphs and Algorithms", John Wiley.
• M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, Linear Programming and Network Flows, Wiley.

Teaching methods

Lectures and exercises.

Assessment methods

The learning assessment takes place through a written test, which has the purpose of examining the acquisition of the knowledge required by the program of the course.

Office hours

See the website of Daniele Vigo

See the website of Marco Antonio Boschetti