OPTIMIZATION
Academic Year 2020/2021 - 1° YearCredit Value: 6
Taught classes: 40 hours
Term / Semester: 1°
Learning Objectives
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 networks 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 in to deal with large-scale optimization problems.
Course Structure
There will be both classroom lessons and laboratory lessons. For each topic, exercises will be solved by the teacher or proposed to students.
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.
Required Prerequisites
Basic elements of vectors and matrices, vector spaces, linear equations, inequalities.
Attendance of Lessons
Attendance is strongly recommended.
Detailed Course Content
Linear Programming (LP) (about 13 h)
LP models; Graphical method; Simplex method; Duality; Sensitivity analysis
Integer Linear Programming (ILP) (about 9 h)
Branch & Bound method; 0-1 programming; Knapsack problem
Software (about 5 hours)
Excel, Mathematica, Wolfram Code, Lingo
Network problems (about 13 h)
Graphs (Kruskal, Dijkstra, Bellman-Kalaba algorithms)
Textbook Information
- J. Stacho, Introduction to Operations Research, Columbia University, NY, http://www.cs.toronto.edu/~stacho/public/IEOR4004-notes1.pdf
- M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, Linear Programming and Network Flows, John Wiley & Sons, 2009.
- F. Hillier, G.J. Liebermann, “Introduction to Operations Research”, McGraw-Hill, 2006
Course Planning
| Subjects | Text References | |
|---|---|---|
| 1 | Simplex Method | 1, 2 |
| 2 | Duality in LP | 1, 2 |
| 3 | Sensitivity Analysis | 1 |
| 4 | Branch & Bound method | 3 |
| 5 | The Knapsak problem | 1, 2 |
| 6 | Graph Algorithms | 1 |
Learning Assessment
Learning Assessment Procedures
The final exam consists of an oral test during which the candidate shows that he has assimilated the topics covered in the course.
Learning assessment may also be carried out on line, should the conditions require it.
Examples of frequently asked questions and / or exercises
The symplex method.
The strong duality theorem.
The Branch & Bound algorithm.
The knapsack problem.
The shortest path algorithm.