Scheda programma d'esame
MATHEMATICAL PROGRAMMING
MAURO PASSACANTANDO
Academic year2020/21
CourseCOMPUTER SCIENCE
Code029AA
Credits6
PeriodSemester 1
LanguageItalian

ModulesAreaTypeHoursTeacher(s)
RICERCA OPERATIVAMAT/09LEZIONI48
MAURO PASSACANTANDO 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 reali, tipicamente di gestione, di allocazione delle risorse e di logistica. Verranno 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 presents the necessary tools for the construction and resolution of optimization models for real problems (management, resource allocation and logistics problems, etc.). The theoretical properties and some of the main algorithmic techniques for the solution of three classes of optimization problems will be illustrated: network flow problems, linear programming problems and integer linear programming problems.

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

Testo di riferimento:

Altri testi consigliati:

  • R.K. Ahuja, T.L. Magnanti, J. Orlin, Network flows. Theory, algorithms and applications, Prentice Hall, 1993
  • G. Bigi, A. Frangioni, G. Gallo, S. Pallottino, M. G. Scutellà, Appunti di Ricerca Operativa, SEU - Servizio Editoriale Universitario di Pisa
  • F.S. Hillier, G.J. Lieberman, Ricerca Operativa - Fondamenti, McGraw-Hill, 2010
  • F. Schoen, Modelli di ottimizzazione per le decisioni, Esculapio, 2006
  • C. Vercellis, Ottimizzazione. Teoria, metodi, applicazioni, McGraw Hill, 2008
Bibliography

Main textbook:

Further textbooks:

  • R.K. Ahuja, T.L. Magnanti, J. Orlin, Network flows. Theory, algorithms and applications, Prentice Hall, 1993
  • G. Bigi, A. Frangioni, G. Gallo, S. Pallottino, M. G. Scutellà, Appunti di Ricerca Operativa, SEU - Servizio Editoriale Universitario di Pisa
  • F.S. Hillier, G.J. Lieberman, Ricerca Operativa - Fondamenti, McGraw-Hill, 2010
  • F. Schoen, Modelli di ottimizzazione per le decisioni, Esculapio, 2006
  • C. Vercellis, Ottimizzazione. Teoria, metodi, applicazioni, McGraw Hill, 2008
Modalità d'esame

Prova scritta seguita da una prova orale. Sono ammessi alla prova orale solo gli studenti che hanno superato la prova scritta. Sono esonerati dalla prova scritta coloro che hanno superato le due prove in itinere/prove di verifica intermedia (nel seguito denominate "compitini"). Sono ammessi al secondo compitino soltanto gli studenti che hanno superato il primo.

Per sostenere la prova scritta dell'esame, inclusi i compitini, è necessario iscriversi entro le date indicate su esami.unipi.it. In genere la scadenza per le iscrizioni è fissata 48 ore prima della prova. In caso di mancata iscrizione da parte di uno o più studenti non è possibile garantire la loro partecipazione alla prova.

Durante la prova scritta non è possibile consultare libri o appunti.

La prova orale viene effettuata nella stessa sessione (Gennaio-Febbraio, Giugno-Luglio, Settembre) della prova scritta secondo un calendario di possibili date comunicato durante il compito e pubblicato contemporaneamente sulla pagina web. La consegna di una prova scritta successiva a quella già superata comporta la rinuncia alla prova precedentemente sostenuta con esito positivo.

Gli studenti che sono stati esonerati dalla prova scritta a seguito di valutazione positiva dei compitini possono svolgere la prova orale in uno dei primi due appelli. La consegna di una prova scritta successiva ai compitini comporta la rinuncia all'esonoro eventualmente già ottenuto.

Assessment methods

The exam is made up of one written test and one oral test. Only students who have passed the written test are admitted to the oral test. Exempted from the written test are those who have passed the two intermediate tests. Only those students who have passed the first intermediate test are admitted to the second intermediate test.

In order to partecipate to the written tests it is necessary to register by the deadlines indicated on exams.unipi.it. If one or more students do not register, it is not possible to guarantee their participation in the test.

During the written test it is not possible to consult books or notes.

The oral test is carried out in the same session (January-February, June-July, September) of the written test according to a calendar of possible dates communicated during the test and published simultaneously on the web page. The delivery of a written test after the one already passed involves the renunciation of the test previously passed with positive results.

Students who have been exempted from the written test following a positive evaluation of the tasks can take the oral test in one of the first two appeals. The delivery of a written test after the tasks involves the waiver of any exemption already obtained.

Updated: 10/09/2020 17:45