==========================================================================
 Corso di Ricerca Operativa 1 da 9 CFU (laurea magistrale e specialistica)
==========================================================================


Finalita` del corso
-------------------

Il corso di Ottimizzazione costituisce una introduzione alla teoria ed
agli algoritmi dell'Ottimizzazione. Vengono trattati gli argomenti
di base della Programmazione Lineare, Programmazione Lineare Intera,
Teoria della Complessita` Computazionale e della Teoria dei Grafi.



Programma del Corso
-------------------

Problemi di ottimizzazione: Programmazione matematica e programmazione
convessa.

Programmazione Lineare (PL) : Generalita`. Modelli di PL.
Geometria della PL. Algoritmo del simplesso: metodo delle 2 fasi,
forma matriciale e tableau, simplesso rivisto. Degenerazione.
Dualita` in PL. Algoritmo del simplesso duale. Analisi di sensitivita`.

Programmazione Lineare Intera (PLI): Modelli di PLI. Totale
unimodularita`. Metodo dei piani di taglio di Chvatal-Gomory.
Algoritmo branch-and-bound. Problema di separazione ed algoritmo
branch-and-cut.

Teoria della Complessita` Computazionale: Classi P, NP, co-NP e problemi
NP-completi. Riduzioni polinomiali.

Teoria dei Grafi: Definizioni. Problemi polinomiali (con modelli ed algoritmi
di risoluzione): albero minimo, cammini minimi, flussi. Problemi NP-completi
(con modelli ed algoritmi di risoluzione): knapsack, commesso viaggiatore,
set covering e set packing, alberi di Steiner, plant location.


Testi consigliati
-----------------

-- M. Fischetti, Appunti di Ricerca Operativa, Edizioni Progetto, Padova, 1995 (tutto)
-- altri esercizi disponibili in rete sul sito del Prof. Alessandro Agnetis (Siena)
	http://www.dii.unisi.it/~agnetis/dispense.html


Esame
-----
Scritto su tutto il programma (compresa teoria e dimostrazioni) senza consultazione testi o appunti.


=========================================
         Operations Research 1 (9 CFU)
=========================================



This course is an introduction to optimization theory and algorithms.
It covers Linear Programming, Integer Linear Programming, Computational
Complexity, and Graph Theory.



Program
-------

Optimization problems: Mathematical programming and convex optimization.

Linear Programming (LP): Introduction. LP models. LP geometry. The simplex
algorithm: the 2-fase method, matrix and tableau forms, simplex revised.
Degeneracy. LP duality. The dual simplex algorithm. Sensitivity analysis.

Integer Linear Programming (ILP): ILP models. Total Unimodularity.
Chvatal-Gomory cutting planes. Branch-and-bound algorithms. Separation
problem and the branch-and-cut algorithm.

Computational Complexity: Classes P, NP, and co-NP. NP-complete problems.
Polynomial reductions.

Graph Theory: Definitions. Polynomially solvable problems: shortest spanning
tree, shortest path, network flow. NP-complete problems: knapsack,
travelling salesman, set covering and packing, Steiner tree, plant location.



Textbooks
---------


-- M. Fischetti, Appunti di Ricerca Operativa, Edizioni Progetto, Padova, 1995
-- see also http://www.dii.unisi.it/~agnetis/dispense.html