Optimisation models and algorithms

Additional Info

  • ECTS credits: 6
  • University: University of L'Aquila
  • Semester: 3
  • 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 7155 times Last modified on Tuesday, 20 February 2018 17:22
Home About Course units Optimisation models and algorithms