00884 - Operations 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

A final examination assesses the achievement of learning objectives:

• knowledge of linear algebra;
• knowledge of derivatives and integral;
• ability to apply the acquired knowledge to simple economic, financial, and business applications.

The final examination consists of a written test, including exercises and theoretical questions, and an oral examination, where the student shows the knowledge and skills acquired during the course. The oral examination is optional and can be done if the student obtain the minimum score of 18/30 in the written examination.

The final score corresponds to the following level of learning achieved: <18 insufficient; 18-23 sufficient; 24-27 good; 28-30 very good; 30L excellent.

Teaching tools

Lecture notes and slides by teacher available online

Office hours

See the website of Marco Antonio Boschetti