Course Details for A.Y. 2013/2014
Name:
Network Optimization [Ottimizzazione Combinatoria II] / Network Optimization [Combinatorial Optimization II]
Basic information
Credits:
: Laurea Magistrale in Informatica 6 CFU (c)
Degree(s):
Laurea Magistrale in Informatica 1° anno curriculum Generale Obbligatorio
Language:
English
Course Objectives
Ability to recognize and model network optimization problems as Integer Linear Programming problems.
Knowledge of fundamental algorithmic techniques for solving large scale Integer Linear Programming problems.
Knowledge of commercial and open source Integer Linear Programming solvers.
Course Content
- Formulations of Integer and Binary Programs: The Assignment Problem; The Stable Set 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; Disjunctive Formulations.
- Optimality, Relaxation and Bounds. Geometry of R^n: Linear and affine spaces; Polyhedra: dimension, representations, valid inequalities, faces, vertices and facets; Alternative (extended) formulations; Good and Ideal formulations.
- LP based branch-and-bound algorithm: Preprocessing, Branching strategies, Node and variable selection strategies, Primal heuristics.
- Cutting Planes algorithms. Valid inequalities. Automatic Reformulation: Gomory's Fractional Cutting Plane Algorithm. Strong valid inequalities: Cover inequalities, lifted cover inequalities; Clique inequalities; Subtour inequalities.
Branch-and-cut algorithm.
- Software tools for Mixed Integer Programming
- Lagrangian Duality: Lagrangian relaxation; Lagrangian heuristics.
- Network Problems: formulations and algorithms.
Constrained Spanning Tree Problems; Constrained Shortest Path Problem; Multicommodity Flows;
Symmetric and Asymmetric Traveling Salesman Problem; Vehicle Routing Problem
Steiner Tree Problem; Network Design.
Local Search
Tabu search and Simulated Annealing
MIP based heuristics
- Heuristics for network problems: local search, tabu search, simulated annealing, MIP based heuristics.
Prerequisites and Learning Activities
Basic knowledge of:
Discrete Mathematics, Linear Programming, Algorithms and Data Structures, Computational complexity.
Knowledge of at least one programming language.
Assessment Methods and Criteria
Written text exam and assignment
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: 19 febbraio 2014, 14:50