Advanced Discrete Optimization

Teacher(s)

Catanzaro Daniele;

Language

English

Main themes

Logic and algorithm

• Logic, automata and context free languages.
• Turing machines. Turing machines build on automata to make it possible to build more elaborate proofs.
• Computability and Complexity theory. Does a problem have an answer? Is the problem well formulated? How can we determine a priori the level of difficulty of a problem?
• Analysis of algorithms.

Content

This course, taught in English, introduces to advanced aspects of integer programming and combinatorial optimization as well as to the main computing techniques used to model and solve practical discrete optimization problems enojoying partitioning, coloring, routing, telecommunications, location, sustainable logistics and supply chain management features. Particularly emphasis is given to the development of problem solving skills as well as to the digitalization aspects, including among others, the ability to transform mathematical formulations of real problems into computer programs able to solve them. 
Table of Contents: computational complexity; efficiently solvable combinatorial optimization problems; matroid theory;  total unimodularity; submodularity; total dual integrality; polyhedral combinatorics; efficient separation / efficient optimization; branch-and-cut. 

Teaching methods

Interactive whiteboard lectures and excercises in the computing rooms. 

Evaluation methods

Assessment is based on continuous work throughout the course and on a research-oriented assignment addressing an advanced topic in integer optimization. The assignment may involve a written report, an oral presentation, or both, depending on the topic selected each year. 

Online resources

Online resources are posted exclusively in the official channel of the course on Microsoft Teams. 

Faculty or entity

> CLSM