OVERVIEW

The teaching unit in Operations Research provides students with skills related to the construction of mathematical models and the use of algorithms to solve decision-making problems formulated as optimization problems.

AIMS AND CONTENT

LEARNING OUTCOMES

The course provides the basic knowldge of optimization methods to solve decision-making problems. In particular, the course will provide knowledge to model from the mathematical viewpoint a decision problem, and solve it through linear programming, linear integer programming, nonlinear programming, and optimization over graphs.

AIMS AND LEARNING OUTCOMES

This teaching unit introduces fundamental concepts and methods in optimization for solving decision problems. In particular, students will acquire the ability to mathematically model decision-making situations and solve them using linear programming, integer linear programming, nonlinear programming, and graph-based optimization techniques.

PREREQUISITES

 Basic knowledge of Mathematical Analysis, Geometry, and Computer Science

TEACHING METHODS

Traditional lessons.

Students with valid certifications for Specific Learning Disorders (SLD), disabilities, or other educational needs are invited to contact the instructor and the Disability Contact Person of the Polytechnic School, Prof. Federico Scarpa (federico.scarpa@unige.it), at the beginning of the course in order to agree on any teaching arrangements that, while respecting the learning objectives, take into account individual learning styles.

SYLLABUS/CONTENT

* Basic concepts in computational complexity theory
* Introduction to mathematical programming and decision problems
* Linear programming with continuous variables: problem formulation, the simplex algorithm, post-optimality analysis, duality theory, and the dual simplex method
* Integer linear programming: binary variables, problem formulation, total unimodularity, cutting planes method, and branch-and-bound algorithm
* Graph optimization: fundamental definitions, the minimum spanning tree problem (Kruskal's and Prim's algorithms); the shortest path problem (Dijkstra, Bellman-Ford, and Floyd-Warshall algorithms)
* Network flows: example formulations, the max-flow min-cut problem and the augmenting path algorithm; the minimum-cost flow problem, cycle-canceling algorithms, and the network simplex algorithm
* Practical examples of modeling and solving linear and mixed-integer programming problems using IBM's CPLEX solver

RECOMMENDED READING/BIBLIOGRAPHY

Handouts provided by the lecturer.

Books for possible further study:

[1] Hillier, Lieberman – Introduction to operations research. McGraw-Hill, 2004.

[2] D. Bertsimas, J.N. Tsitsiklis – Introduction to linear optimization. Athena Scientific, 1999.

All slides used during the lectures and other teaching materials will be available on Aulaweb. In general, the notes taken during the lectures and the materials on Aulaweb are sufficient for exam preparation.

TEACHERS AND EXAM BOARD

LESSONS

LESSONS START

https://corsi.unige.it/en/corsi/10716/studenti-orario

Class schedule

The timetable for this course is available here: Portale EasyAcademy

EXAMS

EXAM DESCRIPTION

Written examination, potentially including:

* Exercises requiring the application of algorithms to the problem classes presented in the course
* Short theoretical questions
* Formulation of simple combinatorial decision-making problems

ASSESSMENT METHODS

By the end of the teaching unit, students are expected to:

* Demonstrate an understanding of the concepts covered in lectures and explain them using appropriate academic language
* Be able to select and apply the most suitable algorithm for solving decision problems presented in the course
* Formulate linear programming models to solve decision problems of a combinatorial nature

FURTHER INFORMATION

For further information not included in the course description, please contact the instructor.