OPERATIONAL RESEARCH
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
- 2022/2023
- Teacher
- MADDALENA NONATO
- Credits
- 6
- Didactic period
- Secondo Semestre
- SSD
- MAT/09
Training objectives
- The aim of the course is to make the student familiar with quantitative approaches for modeling and problem solving. As the complexity of the systems an engineer is likely to deal with, is increasing, decision making is more and more becoming an activity supported by tools developed in the field of mathematical programming. During the course a host of applied OR activities arising in logistics, supply chains transportation and telecommunication will also be discussed and the problem structure exploited to develop ad hoc techniques. Special focus will be on heuristic methods able to deal with large size combinatorial optimization problems.
The acquired expertise concerns the knowledge of the main network problems and algorithms, as well as the abstract knowledge of the main heuristic methods, both constructive and search algorithms, in particular neighborhood based search.
Skills: the course delivers two main abilities. The first is the ability to provide an abstract model to the real combinatorial optimization model to be solved. The second is the ability of exploiting the problem structure to build a solution approach that adapts to the specific problem feature the general theoretical concepts learned during the course, and the ability to recognize a well known combinatorial problem for which polynomial exact solution algorithms are available. Prerequisites
- The student should be familiar with the main topics tought in the Computer Science courses (programming and data structures), Mathematics, and some exposure to Linear Algebra. None is mandatory but it is highly suggested.
Course programme
- Modeling real-life situations as optimization problems, by defining decision variables, objective functions and feasibility constraints. Modeling with 0/1 decision variables.
Algorithms and complexity. Classes P and NP. Approximability.
Network optimization: network terminology and definitions, network design and network flow problems. Solution methods for STP, RC-SPT, project scheduling, MST, max flow, minimum cost flow, assignment and matching.
Gentle introduction to Linear Programming and Integer Linear Programming (definitions and properties, the Simplex algorithm, Branch and Bound) by way of some of the most well known combinatorial optimization problems such as production planning, Knapsack and TSP).
Heuristics algorithms: greedy and ad hoc constructive algorithms for special problems such as S-TSP and A-TSP.
Improvement algorithms: local search and its generalizations, such as neighborhood based Metaheuristics, i.e., GRASP, Tabu Search, Simulated Annealing, VNS, VLNS, as well as population based methods, such as Genetic Algorithms and Scatter Search.
All methods will be exemplified by developping applications to the most well known C.O. problems.
The impact of good modeling is discussed in practice by introducing a commercial sw package for optimization(X-Press MP) and tackling some representative problems. Didactic methods
- The course is delivered by way of theoretical and practical lessons. Team work is encouraged. In particular, open discussion on the modeling part is favored, according to a "Problem Solving Approach" scheme.
Learning assessment procedures
- Passing the exam certifies that the student has gained the expertise and the skills that are listed in the course objectives.
The exam of the "Operations Research" course consists of an oral examination, which is made of two parts. In the first part, the student will present and discuss a project which may have been developed in teams of at most 3 students (team work is highly encouraged but students are required to take the exam at the same time).
The student must apply one or a few methodologies presented during the course in order to solve the problem presented in the project. The programming language used to implement the algorithms is freely eligible, according to the student preferences, and may interact with the XPress package. The first part is awarded a maximum of 22 points. The student will be evaluated according to how well he/she is able to master the chosen solution methodologies.
The second part is made of few oral questions regarding topics discussed during classes.The maximum score of the second part is 10. The “cum laude” requires a minimum total score of 31 points.
The exam may be taken in English upon request. Reference texts
- Teacher's handouts,and specific tutorials giving by the professor.
For further readings, the following textbooks are suggested. All are available at the Library of the Polo Scientifico Tecnologico.
M. Fischietti, Lezioni di Ricerca Operativa; Ed. Libreria Progetto
Padova, 1993.
R. Ahuja, T. Magnanti, J. Orlin; Network Flows; Prentice Hall, 1993.
Hillier F.S. LiebermanG.J., Introduction to Operations Research; Holden-Day, Oackland CA, 1986,(for a general introduction)
A Sassano, Modelli e algoritmi della Ricerca Operativa; Franco Angeli 1999.
X-Press User Guide, www.dashoptimization.com
