Modeling and Solving Constrained Optimization Problems
Responsabile didattico: Luca Di Gaspero
Durata: 28 ore
Periodo didattico: secondo semestre
ProgrammaThe 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.