# Course Details for A.Y. 2013/2014

#### Name:

**Ottimizzazione Combinatoria I / Combinatorial Optimization**

### Basic information

##### Credits:

*:* Laurea in Informatica 6 CFU (c)

##### Degree(s):

Laurea in Informatica 2° anno curriculum Generale Obbligatorio

##### Language:

Italian

### 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.
* *

### Course page updates

This course page is available (with possible updates) also for the following academic years:

** To read the *** current * information on this course, if it is still available, go to the university course catalogue .
*Course information last updated on: 02 luglio 2014, 11:51*