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 7387 times Last modified on Tuesday, 20 February 2018 17:22
Home Structure Semester 2 Course units Optimisation models and algorithms