Combinatorial Optimisation

Credits

Prerequisites

None.

Scientific-disciplinary sector (SSD)

MAT/09 Operations Research.

Examination method

Oral exam and assessment of laboratory work.

Learning
objectives

The main objective of this course is to introduce students to the use of both linear and nonlinear mathematical programming models, with particular attention to integer-variable optimisation models. As regards integer programming models with a finite feasible region (both linear and nonlinear combinatorial problems), the course aims to provide a complete and rigorous treatment of their computational classification. For computationally intractable problems, in addition to exact solution methods, the course also aims to present more sophisticated methods, such as approximation algorithms and heuristic and metaheuristic algorithms.

Syllabus

Introduction to Combinatorial Optimisation. Polynomial-time computable Karp reduction functions. Computational complexity classes. Classification of solution methods. Dynamic programming. Theoretical foundations of greedy methods: matroid theory. Approximation algorithms. Approximation classes. The Minimum Vertex Cover problem for a graph. The Maximum Independent Set problem for a graph. Classification of heuristic methods. Definition of the neighbourhood of a solution. Local search procedures. Metaheuristic algorithms: the 0/1 Knapsack Problem and the Travelling Salesman Problem (TSP); inapproximability theorem; a Branch & Bound algorithm; variants of the TSP. Algorithms for the TSP. Neighbourhood sets of a solution; local search algorithms. Computational complexity analysis of 2-k-opt exchange. Metaheuristics for the standard TSP.

Expected learning
outcomes

By the end of the course, students must demonstrate that they

understand and know the formalisation of (linear and nonlinear) optimisation models for integer programming problems, with particular reference to those with a finite feasible region, as well as the theory and methods of (linear and nonlinear) integer optimisation;
are able to apply the knowledge acquired to model a combinatorial optimisation problem correctly and to solve it correctly by choosing the best method;
are able to communicate ideas and solutions clearly, rigorously and effectively to both specialist and non-specialist audiences;
are able to identify the most appropriate methods to analyse and solve a problem relating to the course topics and to interpret the results correctly.

Learning outcomes
to be assessed

Assessment of the ability to solve exercises of varying difficulty; clarity, correctness and completeness in the written and oral presentation of the course topics.

Combinatorial Optimisation