Modeling and Solving Constrained Optimization Problems

Responsabile didattico: Luca Di Gaspero

Durata: 28 ore

Periodo didattico: secondo semestre


The course will provide the basic knowledge about Constrained Programming and related methodologies for solving real world discrete optimization problems. In particular the topics will be the following ones:

1- Constraint Programming basics: fundamental concepts, types of domains (finite domains, intervals, sets), constraints, search, branch and bound.

2- CP modeling techniques: global constraints, redundant constraints, symmetry elimination, special-purpose constraints (e.g., scheduling), modeling of optimization problems, problem reduction.

3- CP languages/libraries: MiniZinc, ILOG CP Optimizer. Modeling examples: n-Queens, Cryptoarithmetic, Sudoku, Scheduling, Timetabling, ...

4- Basic solution methods: propagation, consistency, search. Advanced solution methods: heuristic methods, hybrid approaches, integration with heuristic/metaheuristic techniques. Statistical analysis of optimization algorithms.

5- Lab practice.

After successful completion of the course, students are able to:

- model and solve combinatorial optimization problems using Constraint Programming (CP);

- implement and compare different methods for solving CP problems.

- select the best heuristic to improve search performance.

Elenco corsi 2022/2023