Informazioni sul corso di
Metodi di Ottimizzazione A.A. 2013/14
•
•
•
•
•
•
•
Orario del corso
Ricevimento e recapiti del docente
MiniSito di ateneo del corso
Mailing list
Modalita’ di Esame
Materiale didattico
Programma
orario
Mercoledi’ 14:10-16:30 aula 5
(da meta’ marzo lab info piccolo)
Venerdi’ 14:10-16:30 aula 5
Curva di attenzione media
durante la prima ora
• Importanza della pausa
• Importanza delle DOMANDE!!!
Ricevimento
• Durante il periodo di lezione mercoledi’ 1718
• Su appuntamento da concordare per mail
• Via skype
Recapiti
•
•
•
•
•
Mail [email protected]
Telefono 0532 97 4994
Mobile 333 4769731
Skype mandolinananato
Ufficio: Dipartimento di Ingegneria,
blocco A piano 3, stanza 313
Files sul sito web
• Vademecum (questo file: riassunto info
principali)
• Elenco progettini (alla fine del corso)
• Slides del corso in tempo reale man mano
che vengono utilizzate
• Files con i modelli sviluppati in laboratorio
• Materiale sul linguaggio Mosel, folder
MoselXpress.zip
• Materiale integrativo
Esame (solo orale)
•
•
•
Obbligo di iscrizione sul sito web di ateneo del corso almeno 3gg lavorativi prima.
Obbligo di cancellarsi se non ci si presenta, e di avvisare per mail.
Possibilita’ di un numero limitato di appelli fuori calendario da concordare con il docente
(opportuno coordinarsi tra gruppi)
•
Orale
–
–
–
•
Votazione
–
–
–
•
Fino a un max di 20/30 punti per il progetto
Fino a un max di 16/30 punti per la tesina compilativa
Fino a un max di 10/30 punti per l’interrogazione orale
Progettini:
–
–
•
Presentazione del progettino o della tesina compilativa
Domande ed esercizi sul programma (TUTTO)
La conoscenza base del linguaggio Mosel e’ obbligatoria anche per chi sceglie di sviluppare il
progettino in un altro linguaggio di programmazione e per chi opta per la tesina compilativa
Lista non vincolante, se fuori lista da concordare col docente
Una volta scelto il progettino occorre mandare una mail al docente con indicato: numero e titolo del
progettino scelto, elenco componenti del gruppo (nome cognome matricola)
Tesina compilativa
–
–
Argomento da concordare col docente
Votazione max 26/30!!
Materiale didattico (in fieri)
•
Testo principale per la programmazione lineare e intera Lezioni di Ricerca
Operativa, Matteo Fischetti, Edizioni Libreria Progetto Padova, 2ed 1999
•
Utile riferimento le dispense del Prof. Federico Malucelli Politecnico di Milano
http://home.dei.polimi.it/malucell/didattica/appunti/materiale.html
•
Slides dal sito web del corso come traccia degli argomenti (non sono dispense!)
•
Documentazione su XPress e Mosel dal sito http://optimization.fico.com da cui
scaricare la versione student del pacchetto XPressMP
•
http://groups.google.co.uk/group/xpressmp/topics gruppo di discussione su
google sull’uso di Xpress
•
Articoli recenti sulle applicazioni (sul sito del corso)
•
Approfondimento (rivolgersi a me)
– Combinatorial optimization in communications networks (springer)
– Routing flow and capacity design in communicatin and computer networks (elsevier).
Programma del corso 13.14
•
•
•
•
•
•
•
•
Introduzione alla programmazione matematica
Programmazione Lineare
Programmazione lineare intera
Esempi di modellizzazione
Rilassamenti e Tecniche di decomposizione
Algoritmi euristici (cenni)
Programmazione bilivello
Ottimizzazione non Lineare (cenni)
Introduzione alla programmazione
matematica
• modelli di ottimizzazione: variabili, classi
principali di vincoli e di funzioni obiettivo.
Esempi di modelli.
• algoritmi e complessità, algoritmi esatti ed
euristici.
Programmazione Lineare
• problemi convessi, geometria della
programmazione lineare,
• metodo del simplesso primale, condizioni
di ottimalità,
• Dualita’, teoremi fondamentali della PL.
• Applicazione del simplesso tramite il
tableau
Programmazione Lineare Intera
• Formulazione di vincoli specifici attraverso
l’uso di variabili booleane.
• Rilassamenti
• Branch and Bound.
• Generazione di colonne, Generazione di
vincoli (metodo cutting plane),
Rilassamento Lagrangeano.
Metodi Euristici: algoritmi
approssimati (cenni)
• errori e schemi di approssimazione
• algoritmi costruttivi: algoritmi greedy e loro
proprietà (matroidi)
• algoritmi di miglioramento:
– ricerca locale
– MetaEuristiche ibride: GRASP e Path
Relinking
Ottimizzazione non Lineare
• Funzioni non vincolata di una sola
variabile (bisezione, Newton) e di piu’
variabili (gradiente).
• Condizioni di ottimalita’ KKT per
l’ottimizzazione vincolata in piu’ variabili.
• Programmazione convessa (metodo di
Frank-Wolfe).
Esempi di modellizzazione con
XPress
uso del linguaggio Mosel e del pacchetto XPress (Laboratorio) per la modellizzazione di
alcuni problemi classici di ottimizzazione
combinatoria:
zaino a variabili binarie, Machine scheduling,
MST, TSP, VRP, Facility Location, Matching,
Vertex Cover, Job-Shop, ….
Implementazione della generazione dinamica di
vincoli e di variabili