
Course unit
OPERATIONS RESEARCH 1
IN11112347, A.A. 2019/20
Information concerning the students who enrolled in A.Y. 2019/20
Mutuated
Course unit code 
Course unit name 
Teacher in charge 
Degree course code 
INL1000878 
OPERATIONS RESEARCH 
MATTEO FISCHETTI 
IN0527 
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 
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.


