Optimisation models and algorithms
Additional Info
- ECTS credits: 6
- Semester: 3
- University: University of L'Aquila
- Lecturer 1: Claudio Arbib
-
Objectives:
Learn algorithmic techniques for important combinatorial optimization problems. Be able to formulate and solve combinatorial optimization problems using integer linear programming. Understand the computational complexity of the problems studied.
-
Topics:
Elements of graph theory and of computational complexity. Combinatorial Optimization (CO) problems. Formulation as 0-1 linear programming. Unimodular and totally unimodular matrices. Hoffmann-Kruskal’s Theorem. Convex hull and ideal formulation of an integer LP. Recursion in CO: optimal paths in a DAG, 0-1 Knapsack. Projection of polyhedra, Fourier-Veronese’s Theorem, Fourier-Motzkin’s Method. Fundamentals of duality theory in LP. Matroids and the Greedy Algorithm: uniform, graphical, partition and vector matroid. Matroid representation and hierarchy. Matching problems. Weak dual inequalities: transversal, stability number, edge-cover and matching. The bipartite case: Gallai’s and König’s Theorem. Guaranteed approximation algorithms for CO: TSP. Polynomial approximation schemes: 01 Knapsack. Linear relaxation of a (mixed) integer linear program. Branch-and-Bound Method. Linear bounds. Dichotomy on a fractional variable. Combinatorial bounds.
-
Prerequisites:
(short survey included in the course): elements of graph theory and of computational complexity
-
Books:
C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity (Dover Publications)
Course slides and exercises freely available from the DISIM website
