Course Details for A.Y. 2013/2014

Course Objectives

Learn advanced algorithmic techniques for some combinatorial optimization problems. Being able to formulate and solve combinatorial optimization problems using integer linear programming

Course Content

• Combinatorial optimization problems. Basic definitions. Examples: (perfect) matching, stable set, vertex cover, edge cover etc. The universal (enumeration) algorithm and its complexity. Dual weak inequalities. Gallai theorem. Berge theorem. Algorithm to find a maximum matching in a graph. Konig theorem. The greedy algorithm. Subclusive combinatorial optimization problems. Exchange property. Matroids. Rado theorem. Linear matroid.
• Optimality, relaxation and bound. “Primal” and “dual” bounds definitions. Relaxation of a linear integer programming problem. Examples of TSP relaxation: 1-tree and 2-matching bound. Held & Karp algorithm to find the minimum 1-tree. Primal bounds for TSP: approximation algorithms (Double Tree, Christofides). The Knapsack 0-1 problem: linear relaxation and primal bound. Bounds from duality. Formulation of combinatorial optimization problems as 0-1 linear programming and their linear relaxation.
• Exact methods to solve combinatorial optimization problems. Branch-and-Bound algorithm. Examples of the Branch-and-Bound application: integer programming problems in two dimensions, Knapsack 0-1, TSP. Dynamic programming algorithm for Knapsack 0-1.
• Totally unimodular matrices. Ideal formulation for integer linear programs. Convex hull definition. Unimodular and totally unimodular matrices definition. Hoffman and Kruskal theorem. Sufficient conditions for the totally unimodularity. Example of an integer linear program whose constraint matrix is totally unimodular: shortest path problem.
• Introduction and comparison among integer programming software.

Prerequisites and Learning Activities

Notion on basic algorithms and linear algebra, linear programming

Assessment Methods and Criteria

written test, oral test if necessary

Textbooks

• W.J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver, Combinatorial Optimization , Wiley.    
• A. Sassano,, Modelli e Algoritmi della Ricerca Operativa , Franco Angeli Editore.    

Internet Resources

Course page updates

• A.Y. 2010/2011
• A.Y. 2012/2013
• A.Y. 2013/2014
• A.Y. 2014/2015
• A.Y. 2015/2016
• A.Y. 2016/2017
• A.Y. 2017/2018
• A.Y. 2018/2019
• A.Y. 2019/2020