Course Details for A.Y. 2017/2018

Course Objectives

Learn algorithmic techniques for some combinatorial optimization problems. Being able to formulate and solve combinatorial optimization problems using integer linear programming. Understand the complexity of the problems studied.

Course Content

• Prerequisites: graphs, definitions and basic properties. Elements of computational complexity: classes P, NP; polynomial-time reduction and the class NP-complete. Examples. Combinatorial optimization problems. Basic definitions. Examples: Transversal (vertex-cover), stable set, dominating set, edge-cover, (perfect) matching, knapsack, graph colouring (chromatic number and index), shortest path, spanning subgraph etc. Formulation as 0-1 linear programming.
• Unimodular and totally unimodular matrices. Necessary conditions, sufficient conditions. Hoffmann-Kruskal’s Theorem. Convex hull and ideal formulation of an integer LP. Examples: shortest path, min-cost flow, bipartite matching, interval graphs.
• Recursion in CO: paths on directed acyclic graphs (DAG) and dynamic programming. Examples of application: optimal paths in a DAG, 0-1 Knapsack. [Projection of polyhedra, systems of linear inequalities, Fourier-Veronese’s Theorem, Fourier-Motzkin’s Method. Fundamentals of duality theory in LP. The Primal-Dual Method. Example of application: Dijkstra’s Algorithm].
• Matroids and the Greedy Algorithm. Definition and characterization of a matroid (Rado’s Theorem). Basics of linear algebra: linear/affine dependence-independence, bases, uniqueness of representation, Steinitz’s (or exchange) Theorem. Examples: trivial matroid, graphical matroid, partition matroid, vector matroid, [matching matroid]. Matroid representation. [An industrial application]. [Rank function, submodular and supermodular set functions. Rank of a matroid. Support function of a convex set. Submodular polyhedron. Lòvasz’s extension. Matroid polyhedron, matroid intersection, intersection of two submodular polyhedra].
• Guaranteed approximation algorithms for CO. Definitions. Polynomial approximation schemes (PTAS, EPTAS, FPTAS). Examples: TSP: double tree and Christofides; Knapsack 0-1.
• Matching (perfect/non-perfect, weighted/unweighted, bipartite/non-bipartite). Weak dual inequalities: transversal, stability number, edge-cover and matching. The bipartite case: Gallai’s and König’s Theorem. [Bi-stochastic matrices and perfect bipartite matching. Non-bipartite matching: matching polyhedron, Edmonds’ Theorem].
• Linear relaxation of a (mixed) integer linear program. Implicit enumeration: the Branch-and-Bound Method. Linear bounds, example: integer Knapsack, 0-1 Knapsack. Dichotomy on a fractional variable. Combinatorial bounds, example: TSP.
• [Separation of an integer polyhedron. Tips on the Ellipsoid Method. Separation and optimization: Finding valid inequalities. Solution of LP with exponentially many variables, example: Min-cut, TSP, 0-1 Knapsack, Stable Set].

Learning Outcomes (Dublin Descriptors)

On successful completion of this course, the student should

Prerequisites and Learning Activities

Notion on basic algorithms and linear algebra, linear programming

Assessment Methods and Criteria

written test, oral test

Textbooks

• W.J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver, Combinatorial Optimization , Wiley. 1997.    
• C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity , Dover Books on Computer Science. 1998. ISBN-13: 978-0486402581, price: used from $6.24, new from $11.51 http://www.amazon.com/Combinatorial-Optimization-Algorithms-Complexity-Computer/dp   
• / A. Sassano,, Modelli e Algoritmi della Ricerca Operativa , Franco Angeli Editore.    

Notes

• Nel semestre di erogazione del corso il docente riceve gli studenti per spiegazioni ogni giovedì dalle 14:30 alle 15:30

Internet Resources

Course page updates

• A.Y. 2016/2017
• A.Y. 2017/2018
• A.Y. 2018/2019
• A.Y. 2019/2020