OPTIMIZATION METHODS
Academic year and teacher
If you can't find the course description that you're looking for in the above list,
please see the following instructions >>
- Versione italiana
- Academic year
- 2021/2022
- Teacher
- MADDALENA NONATO
- Credits
- 6
- Didactic period
- Secondo Semestre
- SSD
- MAT/09
Training objectives
- This course introduces the main mathematical programming tools used to tackle combinatorial optimization problems which can be modeled as Mixed Integer Linear Programming (MILP) optimization problems.
A particular focus will be on applications arising in the TLC field.
Beside theoretical knowledge, the course will provide practical experience in developing and applying the optimization techniques during the lab sessions, in which state of the art optimization software will be used.
Acquired Expertise:
The course teaches how to build an abstract MILP model of a combinatorial optimization problem, defining variables, constraints and objective function.
This process is based on the knowledge of i) the most important families of constraints that model the main types of relationships among entities; ii) the modeling potentials of binary variables; iii) the mathematical properties of the poliedra associated to different families of contraints; iv) the solution techniques that MILP solvers implement.
Skills:
The course delivers the ability to model combinatorial optimization problems, code the model according to a particular algebraic programming language (Mosel for the A.Y. 2015/16), and select the right mathematical programming techniques to speed up the solver performance (XPressMP for the A.Y. 2015/16) Prerequisites
- linear algebra, basic programming skills
Course programme
- Introduction to mathematical programming (convex optimization, constrained and unconstrained optimization, global and local optima).
Linear programming, duality theory.
Integer linear programming, branch and bound, relaxations and decomposition techniques.
Bilevel optimization.
Non linear optimization (basic).
Please, refer to the "Programma del Corso" file for the scheduling information. Didactic methods
- Lectures and lab sessions.
During the lab sessions, the mathematical programming techniques previously introduced during the lectures will be applied to model and solve several optimization problems. A state of the art modelling language such as MOSEL, together with the solver XPressMP (FICO Optimization) will be used. Learning assessment procedures
- - The test is made of an oral examination divided in two parts.
In the fist part, the student can choose: he/she will either present an experimental project, possibly developped as a team work, on a topic select by the teacher, or he/she will present a short survey on one of the topics studied during the course.
The student is encouraged to adopt a presentation software, such as PowerPoint or Prezi, to prepare some slides that illustrate his/her work.
In case of the experimental project, the teacher will evaluate the student work based on how much the student has been able to apply the methodologies taught during the course in tackling the problem addressed in the project.
In case of the survey, the teacher will evaluate the organization, the completeness and the level of details of the relation.
The second part of the exam consists of a traditional oral examination, with questions spanning all topics discussed and presented during the course lectures.
The total score is made of the sum of two partial scores related to the two parts. The maximum for the first part is 21 in case of a project or 17 in case of a survey. The maximum score related to the second part is 11. The "cum laude" requires a total score of 32.
Passing the final exam is the proof that knowledge and abilities outlined in the training objectives of the course have been achieved.
The exam may be taken in English upon request. Reference texts
- The course will be streamed on line and a limited number of students will be physically admitted in the classroom.
A copy of the slides of the lectures is available on the course web site, as well as the material developed during the lab sessions.
More teaching material can be found also on the course web site.
The reference book for Linear and Integer Programming is
"Lezioni di Ricerca Operativa", M. Fischetti, Libreria Progetto, Padova.
As a more in depth reference, see:
Integer Programming, L. Wolsey, Wiley Interscience
