Mathematics for decisions (2020/2021)

Course code
4S008838
Name of lecturer
Romeo Rizzi
Coordinator
Romeo Rizzi
Number of ECTS credits allocated
6
Academic sector
MAT/09 - OPERATIONS RESEARCH
Language of instruction
English
Location
VERONA
Period
I semestre dal Oct 1, 2020 al Jan 29, 2021.

Lesson timetable

Go to lesson schedule

Learning outcomes

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.

Syllabus

- Problems, Instances, Models
- Constraint Programming
- Abstract modeling programming languages - AMPL/GMPL:
- Recall the basics of Linear Programming (if needed)
- Some fact from Polyhedral Combinatorics
- Polytopes, polyhedra and equivalent representations
- Basic lemmas and characterizations
- Integrality of polyhedra
- Solution approaches to NP-hard problems:
- Enumeration
- Implicit enumeration and Branch-and-Bound
- Branch-and-Cut
- Approximation algorithms
- Complete and incomplete formulations (e.g., Traveling Salesman Problem, Perfect Matching)
- Gomory's cuts and cutting planes
- Separation oracles and callbacks
- Compact formulations
- Decomposition techniques:
- Column generation
- Dantzig-Wolfe decomposition
- Isomorphism free generation
- Agent Driven Simulation
- Simulation: its role and some of its techniques
- invitation all'agent driven simulation (ADS) and an introduction to the NetLogo environment

Projects will be proposed during the course, some already at the very beginning, some others from invited companies.
Depending on their interests, students are invited to choose (or even propose and tune together) projects from three categories: industrial, academic, didactics.

COLLECTING A FAIR BACKGROUND:

"Mathematics for decisions" is a 6 credits course that can be seen as a natural continuation of the course of "Operations Research" offered in the Bachelor’s degree in Mathematics, but it 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. They will be welcome by their younger math colleagues.

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).

Finally, we open the course with a mild introduction to polyhedra combinatorics which might offer a sufficient reference and at the same time is new stuff also for the students of mathematics.

Reference books
Author Title Publisher Year ISBN Note
Matteo Fischetti Introduction to Mathematical Optimization (Edizione 1) venduto da Amazon Media EU S.à r.l. 2019 1692792024 disponibile sia la versione cartacea che quella per e-Reader: https://www.amazon.it/Introduction-Mathematical-Optimization-Matteo-Fischetti/dp/1692792024
Robert J. Vanderbei Linear Programming: Foundations and Extensions (Edizione 4) Springer 2001 978-1-4614-7630-6
Robert Fourer, David M. Gay, and Brian W. Kernighan THE AMPL BOOK. AMPL: A Modeling Language for Mathematical Programming   0-534-38809-4

Assessment methods and criteria

The students are required to develop a project. This might either come from industry, from other research centers or universities, from colleagues or on research lines of interest by the department, or even from ourselves included the students themselves).
We also encourage projects that contribute to the rather technical material (TuringArena based) we strive resorting onto in offering active and interactive learning experiences to our students.
We will propose several projects on each one of these main lines, the students are also encouraged to propose and steer themselves according to their interests and competences.

Most projects comprise a development phase where the student must exhibit his/her technical and informatics skills in implementing the models and the algorithms developed or adopted to solve a given problem.

Depending on the project, other phases will be required as part of the exam or might naturally follow:
study of a topic or subject, study of a technique to employ in order to solve a problem or to be illustrated, experiments, deployment, documentation, design of a didactic problem, exposition, writing of paper, stages, thesis, internship.