First cycle
degree courses
Second cycle
degree courses
Single cycle
degree courses
Faculty of Engineering
COMPUTER ENGINEERING
Course unit
OPERATIONS RESEARCH 2
INL1000205, A.A. 2013/14

Information concerning the students who enrolled in A.Y. 2012/13

Information on the course unit
Degree course Second cycle degree in
COMPUTER ENGINEERING
IN0521, Degree course structure A.Y. 2009/10, A.Y. 2013/14
N0
bring this page
with you
Number of ECTS credits allocated 6.0
Type of assessment Mark
Course unit English denomination OPERATIONS RESEARCH 2
Department of reference Department of Information Engineering
Mandatory attendance No
Language of instruction Italian
Branch PADOVA
Single Course unit The Course unit CANNOT 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

ECTS: details
Type Scientific-Disciplinary Sector Credits allocated
Educational activities in elective or integrative disciplines MAT/09 Operational Research 6.0

Course unit organization
Period Second semester
Year 2nd Year
Teaching method frontal

Type of hours Credits Teaching
hours
Hours of
Individual study
Shifts
Lecture 6.0 48 102.0 No turn

Calendar
Start of activities 03/03/2014
End of activities 14/06/2014
Show course schedule 2019/20 Reg.2009 course timetable

Examination board
Board From To Members of the board
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)
8 A.A. 2017/2018 01/10/2017 15/03/2019 FISCHETTI MATTEO (Presidente)
SALVAGNIN DOMENICO (Membro Effettivo)
7 A.A. 2016/2017 01/10/2016 15/03/2018 FISCHETTI MATTEO (Presidente)
SALVAGNIN DOMENICO (Membro Effettivo)
ROMANIN JACUR GIORGIO (Supplente)
6 A.A. 2015/2016 01/10/2015 15/03/2017 FISCHETTI MATTEO (Presidente)
MONACI MICHELE (Membro Effettivo)
ROMANIN JACUR GIORGIO (Supplente)
5 A.A. 2014/2015 01/10/2014 15/03/2016 FISCHETTI MATTEO (Presidente)
MONACI MICHELE (Membro Effettivo)
ROMANIN JACUR GIORGIO (Supplente)
SALVAGNIN DOMENICO (Supplente)
01/10/2013 15/03/2015 FISCHETTI MATTEO (Presidente)
MONACI MICHELE (Membro Effettivo)
SALVAGNIN DOMENICO (Supplente)
3 2012 01/10/2012 15/03/2014 FISCHETTI MATTEO (Presidente)
MONACI MICHELE (Membro Effettivo)
ROMANIN JACUR GIORGIO (Supplente)
SALVAGNIN DOMENICO (Supplente)

Syllabus
Prerequisites: Operations Research 1, computer programming
Target skills and knowledge: Improved know-how on designing and implementing advanced algorithms for combinatorial optimization problems in an effective way.
Examination methods: Traditional with homeworks.
Assessment criteria: Discussion of the methods and algorithms covered.
Course unit contents: Design of advanced combinatorial optimization algorithms and their application to a prototype problem (TSP). Mandatory homeworks requiring the actual implementation of all the proposed techniques will be assigned and checked.
Planned learning activities and teaching methods: Introduction and models for TSP.
1-tree relaxation (HW #1) and recursive B&B (HW #2).
Relaxation by elimination, surrogate and Lagrangian relaxation. Lagrangian duality (plus example).
Subgradient optimization (HW #3).
Lagrangian duality and LP theory, convexification.
Lagrangian duality for TSP and its LP interpretation.
Comparison among alternative subgradient implementations for TSP.
Branching scheme requiring O(n) per node (advanced HW).
K-opt heuristics for TSP (HW #4).
Edge reductions based on incremental 1-tree cost.
ILP model for TSP and its solution through Cplex (HW#5).
Advanced implementations based on Cplex (HW #6).
Miliotis's scheme and use of Cplex callbacks (HW #7).
Connectivity-constraint separation at each node through max-flow (HW #8).
MTZ compact model and its implementation in Cplex (optional HW #9)
Heuristics based on Cplex (Local Branching, RINS, Polish, Proximity) e their computational comparison (HW #10).
Writing a scientific paper (in Latex) on the implemented methods and on the corresponding computational performance(HW #11).
Additional notes about suggested reading: Notes provided by the teacher.
Textbooks (and optional supplementary readings)