icon forward
This is our 2020 curriculum. For the new structure, valid as of the 2021 intake, click here

Optimisation models and algorithms

Additional Info

  • 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 6547 times Last modified on Tuesday, 20 February 2018 17:22
Home Structure for 2020 intake Course units Optimisation models and algorithms

Connect with us

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