Course Details for A.Y. 2011/2012
Name:
Ottimizzazione Combinatoria II / Combinatorial Optimization II
Basic information
Degree(s):
Laurea Magistrale in Informatica 1° anno curriculum Generale Obbligatorio
Language:
Italian
Course Content
- Formulations of Integer and Binary Programs: The Assignment Problem; Set Covering, Packing and Partitioning; Minimum Spanning Tree; Traveling Salesperson Problem (TSP); Formulations of logical conditions
- Mixed Integer Formulations: Modeling Fixed Costs; Uncapacitated Facility Location; Uncapacitated Lot Sizing; Discrete Alternatives
- Geometry of R^n: Linear and affine spaces; Polyhedra: dimension, representations, valid inequalities, faces, vertices and facets; Alternative (extended) formulations; Good and Ideal formulations
- Optimality, Relaxation and Bounds
- LP based branch-and-bound algorithm: Preprocessing, Branching strategies, Node and variable selection strategies, Primal heuristics; Software tools
- Cutting plane algorithm and branch-and-cut algorithm: Chvatal-Gomory cuts: definition and separation procedure; Gomory's fractional cutting plane algorithm; Strong valid inequalities: Clique inequalities for the maximum stable set problem, Subtour inequalities for the TSP, Cover inequalities for the 0-1 knapsack problem; Strengthening valid inequalities: the lifting procedure; Branch-and-cut algorithm
- Lagrangian Duality: Lagrangian relaxation; Lagrangian heuristics
- MIP-Based Heuristics: Dive-and-Fix, Relax-and-Fix, Cut-and-Fix; Local branching, feasibility pump, RINS
- Applications: telecommunication problems: Frequency assignment problem; Network design; Multicommodity flow; Spanning trees with side constraints
Textbooks
- L.A. Wolsey, Integer Programming , Wiley. 1998.
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 marzo 2012, 09:49