Scheda programma d'esame
MATHEMATICAL PROGRAMMING
LUCA MENCARELLI
Academic year2023/24
CourseCOMPUTER SCIENCE
Code029AA
Credits6
PeriodSemester 1
LanguageItalian

ModulesAreaTypeHoursTeacher(s)
RICERCA OPERATIVAMAT/09LEZIONI48
LUCA MENCARELLI unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

Il corso presenta gli strumenti necessari alla costruzione e alla risoluzione di modelli analitici di ottimizzazione per problemi di gestione ed allocazione delle risorse, con applicaizioni in moltissimi campi della scienza e dell'ingegneria ed attività economiche (logistica, trasporti, telecomunicazioni, finanza, energia, salute, ...). Verrà innanzi tutto introdotto il concetto di modellazione matematica per due classi particolarmente rilevanti di problemi di ottimizzazione, la Programmazione Lineare e la Programmazione Lineare Intera, mostrando come sia possibile attraverso di esse costruire modelli di moltissime situazioni reali (o realistiche, o anche completamente immaginarie). Verranno poi illustrate le proprietà teoriche ed alcune delle principali tecniche algoritmiche per la soluzione di tre grandi classi di problemi di ottimizzazione: problemi di flusso su reti, di programmazione lineare e di programmazione lineare intera.

Knowledge

The course introduces the fundamental tools for the construction and solution of analytical optimization models for management and resource allocation problems, with applications in many fields of science and engineering and economic activities (logistics, transport, telecommunications, finance, energy, health, ...). Two particularly relevant classes of optimization problems, Linear Programming and Integer Linear Programming, will be introduced and modelling techniques will be described showing how it is possible to build models of many real (or realistic, or even completely imaginary) situations. The theoretical properties and some of the main algorithmic techniques for the solution of three major classes of optimization problems will then be illustrated: flow problems on networks, linear programming and integer linear programming.

Modalità di verifica delle conoscenze

Esame scritto seguito da prova orale. Sono previste verifiche intermedie (tipicamente tre) che sostituiscono l'esame scritto.

Assessment criteria of knowledge

Written exam plus oral exam. Intermediate written assessments (typically, three) will be held whose successful completion substitutes for the written exam.

Capacità

Lo studente sarà in grado di sviluppare modelli di situazioni reali (o realistiche, o anche del tutto immaginarie) sotto forma di problemi di Programmazione Lineare o Programmazione Lineare Intera. Lo studente sarà quindi in grado di analizzare e sviluppare algoritmi risolutivi per problemi appartenenti a queste classi, tra cui quelli a flusso di rete.

Skills

The student will be able to develop models of real (or realistic, or even completely imaginary) situations under the form of Linear Programs or Integer Linear Programs. The student will then be able to analyse and develop solvution algorithms for problems belonging to these classes, among which netwrok flow ones.

Modalità di verifica delle capacità

Le capacità di modellazione che quelle di analisi e sviuppo di algoritmi saranno verificate sia attraverso l'esame scritto che attraverso l'esame orale.

Assessment criteria of skills

The modeling and algorithm analysis and development skills will be verified both through the written exam and through the oral exam.

Comportamenti

Lo studente potrà sviluppare capacità critiche, sia a livello modellistico che algoritmico, per affrontare problemi di ottimizzazione del mondo reale (o realistici, o anche del tutto immaginari), che risulteranno rilevanti in svariati ambiti lavorativi, sia a livello progettuale che implementativo.

Behaviors

The student will be able to develop critical modelling and algorithmic skills on real-world (or realistic, or even completely imaginary) optimization problems, which will be relevant to several work areas, both at design and implementation level.

Modalità di verifica dei comportamenti

Le capacità critiche dello studente per affrontare problemi di ottimizzazione del mondo reale (o realistici, o anche del tutto immaginari) saranno valutate durante le sessioni di esercitazioni.

Assessment criteria of behaviors

The student's critical skills in dealing with real-world (or realistic, or even completely imaginary) optimization problems will be assessed during the tutorial sessions.

Prerequisiti (conoscenze iniziali)
  • Logica elementare: connettivi logici, proposizioni, principio di induzione, metodi di dimostrazione
  • Spazi vettoriali: spazi, semispazi, vettori, combinazioni lineari, indipendenza lineare, basi, coordinate
  • Geometria del piano e dello spazio tridimensionale: sottospazi affini, equazione di rette, piani e semispazi
  • Prodotto scalare euclideo, ortogonalità
  • Matrici: operazioni con le matrici, determinante, invertibilità
  • Concetto di funzione, funzioni lineari (ed affini)
  • Sistemi lineari di equazioni e loro risoluzione
  • Cosa è un algoritmo
  • Complessità di un algoritmo
  • Classi P e NP
  • Strutture dati: fila, pila, deque, code di priorità, heap
  • Grafi: nodi, archi, alberi, cammini, cicli
  • Grafi: rappresentazione e visite (DFS e BFS)
  • Alberi: rappresentazioni e visite
  • Ricerca dei punti di massimo e minimo di funzioni di una variabile
Prerequisites
  • Boolean logic: operators, propositions, induction principle, proof methods
  • Vector spaces: spaces, semi-spaces, vectors, linear combinations, linear independence, bases, coordinates
  • Geometry of the two and three-dimensional spaces: affine subspaces, equations of lines, planes and half-spaces
  • Euclidean product, orthogonality
  • Matrices: operations with the matrices, determinant, invertibility
  • Affine and linear functions
  • Linear systems of equations and their resolution
  • What is an Algorithm
  • Complexity of an algorithm
  • Classes P and NP
  • Data structures: row, stack, deque, priority queues, heap
  • Graphs: nodes, arcs, trees, paths, cycles
  • Graphs: representation and visits (DFS and BFS)
  • Trees: representations and visits
  • Maximum and minimum points for functions of one variable
Indicazioni metodologiche

Modalità: lezioni frontali, possibilmente con l'aiuto di slides, e sessioni di esercitazioni.   Sito di elearning del corso: download di materiali didattici, pubblicazione di test per esercizi a casa (con relative soluzioni).

Attività di apprendimento: partecipazione alle lezioni e studio individuale.

Frequenza: consigliata

Teaching methods

Delivery: Frontal lessons, possily with the help of slides, exercise sessions.

Course elearning site: download teaching materials, publication of tests for home exercises.

Learning activities: attending lectures, individual study.

Attendance: Advised

Programma (contenuti dell'insegnamento)

Introduzione (2 ore)

  • Problemi decisionali e problemi di ottimizzazione
  • Classi di problemi ed esempi

Modelli e loro formulazione (6 ore)

  • Tipi di variabili: quantitative, logiche, continue, discrete
  • Formulazione di vincoli
  • Formulazione della funzione obiettivo

Grafi e Reti di flusso (16 ore)

  • Modello generale dei problemi di flusso
  • Alberi, cammini e tagli, visite di grafi e alberi
  • Il problema dei cammini minimi
  • Il problema del flusso massimo
  • Il problema del flusso di costo minimo
  • Il problema dell'albero di copertura di costo minimo

Programmazione Lineare (16 ore)

  • Geometria della programmazione lineare e teorema fondamentale
  • Dualità e scarti complementari
  • Basi: complementarità, degenericità ed ottimalità
  • Algoritmi del simplesso primale e duale

Programmazione Lineare Intera (8 ore)

  • Metodi poliedrali: tagli ed algoritmo di Gomory
  • Metodi enumerativi: l'algoritmo "Branch&Bound"
  • Implementazioni ad-hoc per i problemi dello zaino e del commesso viaggiatore
Syllabus

Introduction (2 hours)

  • Decision-making and optimization problems
  • Classes of problems and examples

Optimization models (6 hours)

  • Variables: quantitative, logical, continuous, discrete
  • Constraints formulation
  • Objective function formulation

Graphs and network flows (16 hours)

  • General model for network flow problems
  • Trees, paths and cuts, graph search
  • Shortest path problem
  • Maximum flow problem
  • Minimum cost flow problem
  • Minimum spanning tree problem

Linear Programming (16 hours)

  • Geometry and fundamental theorem of LP
  • Duality and complementary slackness conditions
  • Bases: complementarity, degeneracy and optimality
  • Primal and dual simplex algorithms

Integer Linear Programming (8 hours)

  • Polyhedral methods: Gomory cuts
  • Enumeration methods: the "Branch & Bound" method
  • Ad-hoc implementations of the "Branch & Bound" method for the knapsack problem and the travelling salesman problem
Bibliografia e materiale didattico

Testi di base: Appunti di Ricerca Operativa rilasciati dai docenti. Altro possibile materiale didattico:

  1. Jon Lee A First Course in Linear Optimization Reex Press, 2013
  2. Fabio Schoen Optimization Models, free e-book version, 2022
  3. D. Simchi-Levi, X. Chen and J. Bramel Logic of Logistics: Theory, algorithms, and applications for logistics and supply chain Springer-Verlag, 2004
  4. M.S.Bazaraa, J.J.Jarvis, H.D.Sherali Linear programming and network flows John Wiley & Sons
  5. L.A. Wolsey Integer programming John Wiley & Sons
  6. G. Ghiani, R. Musmanno Modelli e Metodi per l'Organizzazione dei Sistemi Logistici Pitagora, 2000
  7. R.K. Ahuja, T.L. Magnanti, J. Orlin Network flows. Theory, algorithms and applications Prentice Hall, 1993
  8. F.S. Hillier, G.J. Lieberman Ricerca Operativa - Fondamenti McGraw-Hill, 2010
  9. C. Vercellis Ottimizzazione. Teoria, metodi, applicazioni McGraw Hill, 2008

Alcune utili risorse web (software):

Bibliography

Basic material: Lectures in Operations Research (in Italian) released by the lecturers. Other possible textbooks:

  1. Jon Lee A First Course in Linear Optimization Reex Press, 2013
  2. Fabio Schoen Optimization Models, free e-book version, 2022
  3. D. Simchi-Levi, X. Chen and J. Bramel Logic of Logistics: Theory, algorithms, and applications for logistics and supply chain Springer-Verlag, 2004
  4. M.S.Bazaraa, J.J.Jarvis, H.D.Sherali Linear programming and network flows John Wiley & Sons
  5. L.A. Wolsey Integer programming John Wiley & Sons
  6. G. Ghiani, R. Musmanno Modelli e Metodi per l'Organizzazione dei Sistemi Logistici Pitagora, 2000
  7. R.K. Ahuja, T.L. Magnanti, J. Orlin Network flows. Theory, algorithms and applications Prentice Hall, 1993
  8. F.S. Hillier, G.J. Lieberman Ricerca Operativa - Fondamenti McGraw-Hill, 2010
  9. C. Vercellis Ottimizzazione. Teoria, metodi, applicazioni McGraw Hill, 2008

 

Some useful web resources (software):

Indicazioni per non frequentanti

Il testo di base (gratuito) ed i testi di esame scritto (con soluzioni) forniti dai docenti sono più che sufficienti per completare il corso anche non frequentando.

Non-attending students info

The (free) base textbook and the previous written exams (with solutions) are amply sufficient to oass the course even if not attending the lectures.

Modalità d'esame

Esame scritto seguito da prova orale. Sono previste verifiche intermedie (tipicamente tre) che sostituiscono l'esame scritto.

Assessment methods

Written exam plus oral exam. Intermediate written assessments (typically, three) will be held whose successful completion substitutes for the written exam.

Altri riferimenti web

The Commalab Web Page

Additional web pages

The Commalab Web Page

Updated: 26/07/2023 13:37