This site uses only proprietary and third party technical cookies. By continuing to browse the site you are agreeing to our use of cookies. I agree I want to find out more
Browse the Department site:
Browse the Teaching site:

Programme of Course "Network Optimization"

Code:

DT0060

Type of course unit:

Master Degree in Computer Science curriculum SEAS: Compulsory

Level of course unit:

Postgraduate Degrees

Semester:

2nd semester

Number of credits:

Master Degree in Computer Science: 6 (workload 150 hours)

Teachers:

Fabrizio Rossi (fabriziodotrossiatunivaqdotit)

1. 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.

2. Course Contents and learning outcomes (Dublin Descriptors)

Topics of the course include:

  • 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.

On successful completion of this course, the student should

  • Know and define single objective network optimization problems

  • Use and design exact or heuristic algorithms to solve single objective network optimization problems

  • Ability to judge models and methods to tackle network optimization problems

  • Ability to explain the models, the algorithms and the computational complexity needed to solve network optimization problems

  • Ability to learn state-of-art algorithms for network optimization problems

3. Course Prerequisites

Basic knowledge of: Discrete Mathematics, Linear Programming, Algorithms and Data Structures, Computational complexity. Knowledge of at least one programming language.

4. Teaching methods and language

Lectures and software training

Language:English[info]

Reference textbooks

  • L.A. Wolsey, Integer Programming. Wiley. 1998.

5. Assessment Methods

Written text exam and assignment

Course information last updated on: 10 settembre 2015, 10:40