# Course Details for A.Y. 2010/2011

#### Name:

**Ottimizzazione Combinatoria I / Combinatorial Optimization**

### Basic information

##### Degree(s):

Laurea Base in Informatica 3° anno

##### Language:

Italian

### Course Objectives

Apprendere tecniche algoritmiche evolute per alcuni problemi di Ottimizzazione Combinatoria. Capacità di formulare e risolvere problemi di
Ottimizzazione Combinatoria come problemi di Programmazione Lineare Intera

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

Conoscenza della Programmazione Lineare e degli Algoritmi di Base

### Assessment Methods and Criteria

Prova scritta ed eventuale orale

### 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: 06 aprile 2011, 17:01*