# MathMods :: Joint MSc

## Optimisation models and algorithms

• ECTS credits: 6
• Semester: 3
• University: University of L'Aquila
• 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

Read 5332 times Last modified on Tuesday, 20 February 2018 17:22

### Our partners' addresses

#### University of L'Aquila, Italy (UAQ)

Department of Information Engineering, Computer Science and Mathematics, via Vetoio (Coppito), 1 – 67100 L’Aquila (Italy)

#### University of Hamburg , Germany (UHH)

Department of Mathematics
Bundesstr. 55
20146 Hamburg - Germany

#### University of Côte d'Azur, Nice - France (UCA)

Laboratoire J.A.Dieudonné
Parc Valrose, France-06108 NICE Cedex 2