5.00 crédits

30.0 h + 15.0 h

Q1

Enseignants

Catanzaro Daniele;

Langue

d'enseignement

d'enseignement

Anglais

Préalables

*Le(s) prérequis de cette Unité d’enseignement (UE) sont précisés à la fin de cette fiche, en regard des programmes/formations qui proposent cette UE.*

Contenu

This course, taught in English, introduces to the foundations 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: Mathematical Preliminaries; Fundamental problems in linear algebra and number theory; Optimizing over diophantine inequalities with positivity constraints; Optimality, relaxations families and relationships among relaxations, and type of bounds; Efficiently solvable combinatorial optimization problems; Rudiments of computational complexity; General solution approach to optimization over integers; Introduction to polyhedral combinatorics; Branch-and-cut; Fundations of the Mosel programming language and applications.

Table of Contents: Mathematical Preliminaries; Fundamental problems in linear algebra and number theory; Optimizing over diophantine inequalities with positivity constraints; Optimality, relaxations families and relationships among relaxations, and type of bounds; Efficiently solvable combinatorial optimization problems; Rudiments of computational complexity; General solution approach to optimization over integers; Introduction to polyhedral combinatorics; Branch-and-cut; Fundations of the Mosel programming language and applications.

Méthodes d'enseignement

Slided, Blackboard lectures, and Excercises in the Computing room.

Modes d'évaluation

des acquis des étudiants

des acquis des étudiants

Students are assessed individually by means of an exam that consists of two parts:

1. An evaluation of the applied modeling skills, which is usually carried out during the last session of the exercizes and which focuses on the Mosel programming language as well as on the ability to model given toy problems. This part is carried out only once per year and the participation is mandatory for all of the students. A poor score on this part precludes the access to the second part (see point 2).

2. An evaluation of the theoretical skills of the students, carried out by means of a written exam during the standard examination sessions.

In the case of a red code due to the COVID crisis, an oral will replace the written exam mentioned in point 2.

Ressources

en ligne

en ligne

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

Bibliographie

The lectures will be integrated with some capita selecta from the following references: (1) S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press 2004. (2) L. A. Wolsey. Integer Programming. Wiley Interscience, 1988. (3) M. Conforti, G. Cornuejols, G. Zambelli. Integer Programming. Springer, 2014. (4) Bagirov, M. Karmitsa and M. M. Mäkelä. Introduction to non smooth optimization. Springer 2014. (5) F. F. Clarke. Optimization and nonsmooth analysis, Siam 1987.

Support de cours

- Teaching material will be posted in the online resources on Microsoft Teams

Faculté ou entité

en charge

en charge

**CLSM**