9793879 - OPTIMIZATION

This graduated-level course introduces analytic tools and optimization methods that are suitable for large-scale problems arising in data science applications. The course presents both basic and advanced concepts of optimization and explores several algorithms that are efficient for network problems.

The student will acquire the ability to formulate, in mathematical terms, problems related to profit maximization and cost minimization, optimization of resources, and traffic network equilibria.
The goals of the course are:

• Knowledge and understanding: the aim of the course is to acquire advanced knowledge that allows students to study optimization problems and model techniques of large-scale decision-making problems. The students will be able to use algorithms for both linear and nonlinear programming problems.
• Applying knowledge and understanding: students will acquire knowledge useful to identify and model real-life decision-making problems. In addition, through real examples, the student will be able to implement correct solutions for complex problems.
• Making judgments: students will be able to choose and solve autonomously complex decision-making problems and to interpret the solutions.
• Communication skills: students will acquire base communication and reading skills using technical language.
• Learning skills: the course provides students with theoretical and practical methodologies and skills  to deal with large-scale optimization problems.

There will be both classroom lessons and laboratory lessons. For each topic, exercises will be solved by the teacher or proposed to students. During the course notes on some topics will be given. Moreover, a very detailed description of everything explained in classroom will be posted on Studium.  Students are invited to carefully check this description before they take the exam.

Should teaching be carried out in mixed mode or remotely, it may be necessary to introduce changes with respect to previous statements, in line with the programme planned and outlined in the syllabus.

Recall of Linear Algebra (about 6 hours)

Linear Programming (LP) (about 13h)
LP models; Graphical method; Simplex method; Duality; 

Integer Linear Programming (ILP) (about 8 h)
The maximum weight matching problem;  The minimum vertex cover problem; Basics of the Branch & Bound method; examples of 0-1 programs;

Software (about 5 hours)
Excel,Matlab,

Network problems (about 8 h)
Graphs (Kruskal, Dijkstra)

1. M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, Linear Programming and Network Flows, John Wiley & Sons, 2009.
2. F. Hillier, G.J. Liebermann, “Introduction to Operations Research”, McGraw-Hill, 2006
3. Matoušek-Gärtner: Understanding and using linear programming, Springer 2007
4. S. Lipshutz, M.L. Lipson, Linear Akgebra,SCHAUM's outline series, Mc Graw Hill, NY, 2009
   

The profit evaluation consists of a written test, which is compulsory and of an optional oral examination. The oral examination can only be taken by students who obtain a mark equal or greater than 18 in the written test.

The written test consists of one exercise and the student will also be asked to provide some basic concepts of the course, illustrated with examples. Moreover, the description of one of the classical problems presented in the course will be asked. Proofs of theorems will not be asked in the written test. 

  Students who pass the written test will receive a mark from 18 to 27 and can either accept it as the final mark or ask to continue the exam with an in-depth discussion on the topics of the program. In this case, after the oral discussion a new mark will be proposed to the student, which can be higher

(up to 30 e lode) or lower than the mark of the written test.

Least square method

Method of absolute deviation

Basic Feasible solutions

Pivoting rules

The maximum weight matching problem

The minimum vertex cover

Kruskal Algorithm