METHODS AND MODELS FOR COMBINATORIAL OPTIMIZATION

Second cycle degree in COMPUTER SCIENCE

Campus: PADOVA

Language: English

Teaching period: First Semester

Lecturer: LUIGI DE GIOVANNI

Number of ECTS credits allocated: 6


Syllabus
Prerequisites: Basic notions of Operations Research, Linear Programming, and computer programming.
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.
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.