
Course unit
OPERATIONS RESEARCH
INL1000878, A.A. 2019/20
Information concerning the students who enrolled in A.Y. 2019/20
ECTS: details
Type 
ScientificDisciplinary Sector 
Credits allocated 
Educational activities in elective or integrative disciplines 
MAT/09 
Operational Research 
9.0 
Course unit organization
Period 
First semester 
Year 
1st Year 
Teaching method 
frontal 
Type of hours 
Credits 
Teaching hours 
Hours of Individual study 
Shifts 
Lecture 
9.0 
72 
153.0 
No turn 
Examination board
Board 
From 
To 
Members of the board 
10 A.A. 2019/2020 
01/10/2019 
15/03/2021 
FISCHETTI
MATTEO
(Presidente)
SALVAGNIN
DOMENICO
(Membro Effettivo)
FERRANTE
AUGUSTO
(Supplente)
FERRARI
CARLO
(Supplente)

9 A.A. 2018/2019 
01/10/2018 
15/03/2020 
FISCHETTI
MATTEO
(Presidente)
SALVAGNIN
DOMENICO
(Membro Effettivo)
FERRANTE
AUGUSTO
(Supplente)
PIETRACAPRINA
ANDREA ALBERTO
(Supplente)

Prerequisites:

Basic notions of computer science and matrices 
Target skills and knowledge:

This course will provide knowledge about Optimization techniques such as Linear Programming, Integer Linear Programming, Computational Complexity, and Graph Theory. Il will provide the student with the capability of modeling and solving complex optimization problems. 
Examination methods:

Traditional 
Assessment criteria:

Written examination 
Course unit contents:

Optimization problems. Linear Programming (LP). Integer Linear Programming (ILP). Computational Complexity. Graph Theory. Polynomially solvable problems. NPcomplete problems 
Planned learning activities and teaching methods:

Optimization problems: Mathematical programming and convex optimization.
Linear Programming (LP): Introduction. LP models. LP geometry. The simplex algorithm: the 2phase method, matrix and tableau forms, simplex revised.Degeneracy. LP duality. The dual simplex algorithm. Sensitivity analysis.
Integer Linear Programming (ILP): ILP models. Total Unimodularity. ChvatalGomory cutting planes. Branchandbound algorithms. Separation problem and the branchandcut algorithm.
Computational Complexity: Classes P, NP, and coNP. NPcomplete problems. Polynomial reductions.
Graph Theory: Definitions.
Polynomially solvable problems: shortest spanning tree, shortest path, network flow.
NPcomplete problems: knapsack, travelling salesman, set covering and packing, Steiner tree, plant location. 
Textbooks (and optional supplementary readings) 

Matteo Fischetti, Lezioni di Ricerca Operativa. Padova: Progetto, 1999.


