Schema della sezione

  • Introduzione

    Minimizza tutto Espandi tutto

  • Timetable & Contacts

    Academic Year 2024/25, Second Semester, 6CFU (48 hours)


    Lecturer: Antonio Frangioni


    Timetable of the course

    • ??days, ??:00 - ??:00, Room Fib ??
    • ??days, ??:00 - ??:00, Room Fib ??

    Team of the lectures (to be updated)


    Lectures' Log (registro delle lezioni) - to be updated


    Students' time (ricevimento): Tuesdays, 9:00 - 11:00, or at any other time by arranging an appointment by e-mail, Team for students' time


  • Description and Program

    The course will, through presentation of actual working cases and project work, enable the student to produce and/or appropriately use software tools for the support to complex decisions (mainly at the corporate/industrial level), in particular those based on mathematical optimization techniques. The course is focused on practical aspects of these tools (modeling languages and systems, solvers and interfaces, algorithmic parameters, ...) and has a strong project aspect in order to familiarize the students, in particular, with the specific computer science aspects of these activities. However, since these tools are based on complex algorithmic schemes and rigorously defined mathematical properties, it is at the same time necessary to provide the students with appropriate consciousness of these foundational aspects, in particular whenever this is necessary to better understand their use or design more efficient and effective approaches; a particularly relevant case is that of handling the issue of uncertainty in the data of the problem.

    Program:

    1. Introduction (6 hours)

      • Decision theory, the decision process in a business environment

      • Structure of Model-Driven Decision Support Systems

    2. Review of mathematical optimization (10 hours)

      • Linear Programming (LP) problems

      • Integer Linear Programming (ILP) problems

      • Algorithms for LP

      • Algorithms for ILP

    3. LP and ILP solvers (16 hours)

      • LP and ILP solvers: software structure.

      • Instances: API, modeling languages, modeling systems

      • Practical issues in the solution of LPs and ILPs

    4. Methodologies to improve solver effectiveness (16 hours)

      • The general principle: develop a better formulation

      • Cutting planes

      • Dynamic programming

      • Column generation and decomposition

  • Textbooks, material, and useful links

    The main material for the course will be the lectures, that will be streamed on the Teams, recorded and available on this page, plus software and data that will also be distributed here.

    A few textbooks and references that may be useful for the course are:

    1. basic Operations Research course material (in Italian, download link below)
    2. Jon Lee A First Course in Linear Optimization Reex Press, 2013
    3. Fabio Schoen Optimization Models, free e-book version, 2022
    4. D. Simchi-Levi, X. Chen and J. Bramel Logic of Logistics: Theory, algorithms, and applications for logistics and supply chain Springer-Verlag, 2004
    5. M.S.Bazaraa, J.J.Jarvis, H.D.Sherali Linear programming and network flows John Wiley & Sons
    6. L.A. Wolsey Integer programming John Wiley & Sons
    7. G. Ghiani, R. Musmanno Modelli e Metodi per l'Organizzazione dei Sistemi Logistici Pitagora, 2000

    Links to useful web resources (mostly software) are:

  • Assessment

    Grading for the exam is divided in two parts: a project and an oral examination. The latter can only be held after that the project has been completed and formally approved.

    There are two types of possible projects, as described in the "Didactic projects" section below, plus it is always possible for (groups of) students to spontaneously propose their own subjects.

    The project is designed to be performed in groups of 2 students. Within a specified date, to be posted on this page, the students are requested to organize themselves in groups of two, with exceptions to be explicitly agreed upon with the lecturer. Groups will have to be communicated to the lecturer by e-mail with a single text file describing all groups with the format

    Group 1
    • Name, Surname, matricola, e-mail address
    • Name, Surname, matricola, e-mail address
    Group 2
    • Name, Surname, matricola, e-mail address
    • ...

    Once that the list of groups is established, the lecturer will provide a list of possible project assignments for the groups to choose from. However, spontaneous proposals from (groups of) students are welcome and encouraged; of course the lecturer reserves the right to request amendments to the proposals, and even dismiss them outright. Any group that succeeds in having a spontaneous proposal accepted will have the right to perform the corresponding project. All other groups will be required, within a specified date, to agree among themselves a (partial) matching between groups and available assignments, and to provide the result to the lecturer by e-mail with a single text file describing it with the format

    Group 1 --> Project n. X
    Group 2 --> Project n. Y
    ...


    Of course, each project can be assigned to at most one group. If some of the groups cannot resolve their dispute about some particular assignment, all the interested groups will be assigned a random project among these left free from the collaborative groups.

    The outcome of each project will primarily be a written report (exclusively PDF, use of LaTeX is suggested but not mandatory) detailing all the steps as specified in the projects proposals document. It is advised (but not mandatory) that the report of the project is sent to the lecturer incrementally, so that each step can to be checked in order to avoid that methodological errors at some stage lead to wasted work at later stages. The dates of delivery of (each step of) the project are entirely flexible. Only after that the report is completely approved the group will also have to send to the lecturer (in a single compressed .zip, .gzip or .tgz file) a distribution of all the material (models, data, scripts, spreadsheets, ...) having been produced to fulfill the required tasks. Once the distribution is also accepted, the project is approved.

    Once the project is approved, a date for the oral exam will be freely agreed upon between the lecturer and the group (the concept of "sessione d'esame" does not apply to this course). It is required that all the members of the group take the oral exam simultaneously; exceptions will have to be explicitly requested, and will only be granted for serious reasons. The oral exam consists in a discussion of the project results and possible variants/extensions, and can therefore comprise any subject within the program of the course. The grade of the project (which will not be formally stated by the lecturer, but will be clear during the required interaction) will significantly contribute to the final grade of the exam. Once a project is approved, it (and the corresponding grade) is valid for all the academic year; asking for a new project in order to increase the grade is not allowed. Repeating the oral exam is technically possible but discouraged; any subsequent attempt at the oral exam will necessarily have to forego the discussion of the project, and will therefore include a more in-deep discussion of the theoretical aspects of the course.

  • Recordings of lectures

  • Software and data

    The material will be added progressively as the course unfolds.

  • Didactic projects

    There are two possible forms of didactic projects:

    • "Normal projects", that require the implementation of a (prototype) Decision Support System based on mathematical optimization techniques, i.e., the practical solution of one optimization problem using the tools and techniques discussed during the course, or whatever more appropriate tool and technique the students may choose to employ (although prior consultation with the lecturer is advised in this case). For these projects, the students are completely free to chose the tools (programming languages, modelling tools, mathematical optimization solvers, ...).
    • "SMS++ projects", whereby the students are required to use the Structured Modelling System framework as the modelling tool, which implies the choice of C++ as the programming language. These projects may require either the development of a Block (model of a specific optimization problem), or of a Solver (specialised solution algorithm) for an existing Block, or both.
    While the overall difficulty of the two projects is analogous, SMS++ projects have more stringent requirements on both the tools used and the required quality of the produced software, and are therefore by default considered more favorably in term of final grading.

    It is always possible, and welcome, for the groups to spontaneously propose projects, of either type, which of course will have to be discussed with, and approved by, the lecturer, possibly after amendments.

    A list of proposals for didactic projects, of either type, will be made available in due time.