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 and Optimization Problems

Definition of a mathematical model: decision variables, objective function, and constraints. Mathematical modeling techniques.

Examples of mathematical models for real-world applications.

2. Linear Programming (LP) and Integer Programming (IP)

Linear programming models with continuous variables. Graphical solution of LP problems. Linear programming theory and the simplex algorithm.

Linear programming models with integer variables. Geometric interpretation. Properties of integer programming problems. Relaxation techniques. Cutting-plane algorithms. The branch-and-bound method (B&B).

3. Fundamentals of Graph Theory and Applications

Basic definitions and concepts of graph theory. Minimum spanning trees. Shortest-path problems. Network flow problems: maximum flow and minimum-cost flow.

Readings/Bibliography

Lecture notes and slides by teacher available online

Further reading on lecture topics:

• Matteo Fischetti, Lezioni di Ricerca Operativa, Libreria Progetto.
• 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:

• the ability to formulate mathematical models for optimization problems;
• knowledge of methods and algorithms for continuous, integer, and mixed-integer linear programming;
• knowledge of the fundamentals of graph theory and of the basic methods and algorithms for solving selected graph-theoretic problems.

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.

During the examination, students may use only a non-programmable scientific calculator.

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