Teaching code

4S008838

Teacher

Coordinator

Credits

6

Language

English

Scientific Disciplinary Sector (SSD)

MAT/09 - OPERATIONS RESEARCH

Period

Semester 1 dal Oct 3, 2022 al Jan 27, 2023.

Lessons timetable Moodle Seminars 0

Learning objectives

Mathematics for decisions is a seminar course comprising: + interventions by external professors (seminars, mini-courses); + interventions by professionals (statements of problems from the applications, description of needs and/or projects); + interventions by the referent of the course, collaborators of him, or colleagues by the department (both classes and proposal of problems and projects from the applications). + presentations delivered by the students on arguments of their interests and as agreed upon (seminars). The aim of this offert is to provide the studens with opportunities to meet and/or get involved into working or research projects, activating and developing their own interests, motivations and talents. Among the targets of this offert: + provide the students with opportunities to get in touch with working and/or research environments, developing motivations, interests, attitudes; + allow connections with professionalities and disciplines, not necessarily within mathematics but that can motivate the work of a matematician or help appreciating its possible applicability; + stimulate and develope the competence in designing mathematical models for the managing of production facilities, networks, and services; + provide the students with occasions to experiment their computational and informatics skills and to become more aware of their impact and role. With this the aim is to lead our students to: + have the competence and attitude to cover technical and professional roles with an high-level modellistic-math profile; + have the necessary starting background and the attitude to document themselves by accessing math texts, research articles, project deliverables, technical documentation.

Prerequisites and basic notions

“Mathematics for decisions” is a 6-credit course that can be seen as a natural continuation of the course of “Operations Research”, offered in the Bachelor’s degree in Mathematics and mandatory for all students.
Anyway, this course is also recommended to Computer Science students with interests in algorithms, mathematics, and optimization.

The prerequisites from the “Operations Research” course divide in two groups:

+ the methodology and the bones of concrete mathematics: invariants, good characterizations, induction, dynamic programming, algorithms, data structures, complexity. The CS students may get these with the course in Algorithms at the bachelor and then in the Algorithms and Complexity course in the first year of the master.

+ the fundamentals of Linear Programming: we encourage the CS students to collaborate in collecting this background. We are available in suggesting materials, and open at guesting them at the few lessons of pertinence in the “Operations Research” course.

Also, our approach in the Math Decisions course will be rather pragmatic, thus the theoretical knowledge will not be that necessary after all (though it is certainly a pity and a weakness not to have the whole picture).

Program

- Problems, Instances, Models
- Basic notions of Linear Programming and Integer Linear Programming
- Introduction to the Gurobi solver
- Some concepts of Polyhedral Combinatorics:
- Polytopes, polyhedra and equivalent representations
- Basic lemmas and characterizations
- Convex Hull
- Integer polytopes
- Classical Operations Research problems and their formulations (e.g., Knapsack, Set Covering, Network, Scheduling, Routing, etc.)
- Modelling techniques in Integer Linear Programming
- Approaches for solving NP-hard problems:
- Exact algorithms:
- Enumeration
- Implicit and Branch-and-Bound Enumeration
- Cutting Planes
- Separation oracles and callbacks
- Branch-and-Cut
- Complete and incomplete formulations (e.g., Traveling Salesman Problem, Perfect Matching)
- Compact formulations
- Approximation algorithms
- Heuristic algorithms:
- Local search
- Constructive heuristics
- Metaeuristics and matheuristics
- Advanced decomposition techniques

Bibliography

Didactic methods

The course will be held in presence in the classroom. Anyway, all lectures will be recorded with Zoom and uploaded to Panopto, in order to give the possibility to recover them to those unable to attend. The rights of students will be preserved in situations of travel limitation or confinement due to national provisions to combat COVID or in particular situations of fragile health. In these cases, you are invited to directly contact the teacher to organize the most appropriate remedial strategies.

Learning assessment procedures

In order to pass this course, students will have to do a written exam and to develop a project, which will be presented and assigned during the course.
The project may come from us, or from the industrial world, from other research centers or universities, from colleagues or from research lines in the department.
The project typically includes a development phase where students demonstrates that they are able to acquire the technical and IT skills to implement the algorithms and models studied or developed, in order to solve a given problem.
The project can be developed individually or by groups. The evaluation of the project will consist in the drafting of a document and a short oral discussion.

Evaluation criteria

Modelling skills
Knowledge of the paradigms of Linear Programming, Integer Linear Programming, Mixed Integer Linear Programming, and of the main modelling techniques
Knowledge of exact and heuristic methods
Ability to independently solve an optimization problem
Understanding of a scientific article not discusses in the classroom
Ability to synthesize and present

Criteria for the composition of the final grade

A) Written exam: maximum 30 points.
B1) Midterm presentation about a scientific paper in a flipped-classroom modality: maximum 5 points.
B2) Final project: maximum 25 points.
Final grade: average of A and (B1 + B2).

Exam language

English