First cycle
degree courses
Second cycle
degree courses
Single cycle
degree courses
School of Science
COMPUTER SCIENCE
Course unit
METHODS AND MODELS FOR COMBINATORIAL OPTIMIZATION
SC01122975, A.A. 2017/18

Information concerning the students who enrolled in A.Y. 2016/17

Information on the course unit
Degree course Second cycle degree in
COMPUTER SCIENCE
SC1176, Degree course structure A.Y. 2014/15, A.Y. 2017/18
N0
bring this page
with you
Number of ECTS credits allocated 6.0
Type of assessment Mark
Course unit English denomination METHODS AND MODELS FOR COMBINATORIAL OPTIMIZATION
Website of the academic structure http://informatica.scienze.unipd.it/2017/laurea_magistrale
Department of reference Department of Mathematics
Mandatory attendance No
Language of instruction English
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 LUIGI DE GIOVANNI MAT/09
Other lecturers MARCO DI SUMMA MAT/09

Mutuated
Course unit code Course unit name Teacher in charge Degree course code
INP5070470 METHODS AND MODELS FOR COMBINATORIAL OPTIMIZATION LUIGI DE GIOVANNI IN2191

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

Mode of delivery (when and how)
Period First semester
Year 2nd Year
Teaching method frontal

Organisation of didactics
Type of hours Credits Hours of
teaching
Hours of
Individual study
Shifts
Practice 0.5 4 8.5 No turn
Laboratory 1.5 12 25.5 No turn
Lecture 4.0 32 68.0 No turn

Calendar
Start of activities 02/10/2017
End of activities 19/01/2018

Examination board
Examination board not defined

Syllabus
Prerequisites: Basic notions of Operations Research, Linear Programming, and computer programming.
Target skills and knowledge: Basic use of advanced decision support methods for modelling and solving combinatorial optimization problems. Use of mathematical and algorithmic tools for solving optimization problems of practical relevance by software packages and optimization libraries.
Examination methods: Oral examination about course contents. Each student may chose to present a short project concerning models and exact/heuristic solution methods for a realistic application of combinatorial optimization.
Assessment criteria: The examination evaluates to what extent the student has learned the notions presented and her/his ability to apply them to the solution of practical combinatorial optimization problems.
Course unit contents: 1. Advanced linear programming and duality with applications: primal-dual simplex, column generation, applications to network
optimization.
2. Advanced methods for Integer Linear Programming (ILP): Branch & Bound and relaxation techniques, alternative ILP formulations,
cutting planes method and Branch & Cut, application to relevant examples (Traveling Salesman Problem, location, network design etc.).
3. Meta-heuristics for combinatorial optimization: local search based, evolutionary algorithms.
4. Application of graph modeling and optimization.
5. Labs: optimization software packages and libraries.
Planned learning activities and teaching methods: Classes. Labs. Discussion about case studies. During labs, some basic optimization algorithms will be implemented, both exact (using integer programming libraries) and heuristic.
Additional notes about suggested reading: Lecture notes provided by the teacher. Articles from scientific journals.
Textbooks (and optional supplementary readings)