MathMods :: Joint MSc

Additional Info

• ECTS credits: 6
• University: University of L'Aquila
• Semester: 3
• Lecturer 1: Claudio Arbib
• Objectives:

   

   

• Topics:

   

   

  Introduction to optimization: linear, nonlinear and discrete optimization. Combinatorial optimization (CO) and its relation to linear programming (LP). Relevant CO problems, their 01 LP formulations and the universal algorithm.
  System of linear inequalities, projections, Fourier-Veronese’s Theorem, Fourier-Motzkin’s Method. Theorems of the alternative and duality theory in LP. Examples and interpretations.
  Matroids and the greedy algorithm. Rado’s Theorem. Trivial, graphic, vectorial, partition and matching matroid. Submodular set functions.
  Algorithms and bounds for special problems. Dynamic programming, examples of application to optimal paths and to knapsack. Shortest path and Dijkstra algorithm. Bipartite matching, algorithms for the unweighted and the weighted case.
  A general algorithm: branch-and-bound.
  Approximation algorithms. Examples: 01 knapsack and metric TSP.
  A real industrial application.

• 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