First cycle
degree courses
Second cycle
degree courses
Single cycle
degree courses
School of Engineering
COMPUTER ENGINEERING
Course unit
OPERATIONS RESEARCH 1
IN11112347, A.A. 2019/20

Information concerning the students who enrolled in A.Y. 2019/20

Information on the course unit
Degree course Second cycle degree in
COMPUTER ENGINEERING
IN0521, Degree course structure A.Y. 2009/10, A.Y. 2019/20
N0
bring this page
with you
Number of ECTS credits allocated 9.0
Type of assessment Mark
Course unit English denomination OPERATIONS RESEARCH 1
Department of reference Department of Information Engineering
Mandatory attendance No
Language of instruction Italian
Branch PADOVA
Single Course unit The Course unit can be attended under the option Single Course unit attendance
Optional Course unit The Course unit can be chosen as Optional Course unit

Lecturers
Teacher in charge MATTEO FISCHETTI MAT/09

Mutuated
Course unit code Course unit name Teacher in charge Degree course code
INL1000878 OPERATIONS RESEARCH MATTEO FISCHETTI IN0527

ECTS: details
Type Scientific-Disciplinary 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

Calendar
Start of activities 30/09/2019
End of activities 18/01/2020
Show course schedule 2019/20 Reg.2009 course timetable

Syllabus
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. NP-complete 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 2-phase 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 (and optional supplementary readings)
  • Matteo Fischetti, Lezioni di Ricerca Operativa. Padova: Progetto, 1999. Cerca nel catalogo