Academic Year 2023-2024

OPTIMIZATION

Teachers

Franca Rinaldi
Course Year
3
Unit Credits
6
Teaching Period
First Period
Course Type
Characterizing
Prerequisites. Main topics in linear algebra and affine geometry
Teaching Methods. Theoretical lessons and exercises
Verification of Learning. The exam consists of a written test and an oral exam. The written exam consists of some exercises to test the student’s ability to apply the theoretical and methodological knowledge acquired in the course to the resolution of numerical instances, the formulation of models and the proof of easy statements. The oral test consists of some general theoretical questions and aims to verify the knowledge and the ability to present the contents of the course.

The grades will be determined based on the criteria approved by the Course Council available at the link

https://www.uniud.it/it/didattica/corsi/area-scientifica/scienze-matematiche-informatiche-multimediali-fisiche/laurea/matematica/studiare/criteri-guida-di-assegnazione-del-voto-degli-esami-di-profitto/view

More Information. Any two years a laboratory takes place where the students can learn how to use the modelling language AMPL and the main LP/ILP solvers to model and solve some problems of both applicative and theoretical type.
Objectives
At the end of the course the student will:

– Knowledge and understanding: know the fundamental properties of the convex sets; know the theory, the main methodologies, the computational aspects and some classical applications of linear programming; know the theory, the main methodologies and the computational aspects of integer linear programming and the ILP models of some classical combinatorial problems; know the main concepts and problems of the graph theory and their complexity.

– Applying knowledge and understanding: be able to formulate an LP/ILP model for simple combinatorial/real-life problems; be able to apply duality arguments to solve pairs of primal-dual LP problems; be able to solve simple LP/ILP instances using the appropriate algorithms; be familiar with the technique of sensitivity analysis.

– Autonomy of judgment: be able to identify a suitable LP/ILP/graph model for simple combinatorial/real-life problems.

– Communication skills: be able to present the subjects of the course with rigor and completeness.

– Learning skills: be able to further deepen the course topics in relation to aspects not performed in class.

Contents
The course covers three fundamental topics in mathematical optimization: Linear Programming (LP), Integer Linear Programming (ILP), and Graph Theory. For each topic, the theoretical foundations and the solution methodologies are presented, and the computational aspects are discussed. Additionally, the process of modeling a problem as an LP or ILP is illustrated through numerous theoretical and applied examples. In the early lectures, elements of convex analysis and computational complexity are also introduced.
Texts
– Paolo Serafini, “Ottimizzazione”, Zanichelli, Bologna 2000

– Lecture notes and other teaching material made available by the teacher