- Docente: Valentina Cacchiani
- Credits: 6
- SSD: MAT/09
- Language: English
- Teaching Mode: Traditional lectures
- Campus: Bologna
-
Corso:
Second cycle degree programme (LM) in
Telecommunications Engineering (cod. 9205)
Also valid for Second cycle degree programme (LM) in Electronic Engineering (cod. 0934)
Second cycle degree programme (LM) in Mathematics (cod. 5827)
Second cycle degree programme (LM) in Automation Engineering (cod. 8891)
Second cycle degree programme (LM) in Automation Engineering (cod. 8891)
Second cycle degree programme (LM) in Electrical Energy Engineering (cod. 9066)
-
from Sep 21, 2023 to Dec 15, 2023
Learning outcomes
Integer Programming is a very powerful tool for modeling combinatorial optimization problems arising in many branches of engineering, industry and resource allocation. The first part of this course covers the modeling aspects of the field, providing the tools for constructing effective mathematical models, i.e., models that can be solved in practice. The second part is devoted to the algorithmic aspects: basic algorithms are reviewed and more sophisticated ones, useful for those models characterized by a large number of variables and/or constraints, are presented in detail. Finally, the third part of discusses real-world applications.
Course contents
Requirements: a good knowledge of linear algebra and basic mathematics is required.
The course is given in English: slides and exercises are in English. The exam must be taken in English.
The course focuses on optimization problems arising in decision making and the definition of mathematical models and exact algorithms to solve them. The mathematical theory on which these methods are based is elaborated through the study of theorems.
Contents
- Introduction to optimization problems arising in decision making and to Mathematical Programming
- Convex programming, Linear Programming, simplex algorithm, duality theory
- Integer Linear Programming, branch-and-bound algorithm, classical combinatorial optimization problems, relaxations, computational complexity
- Exponential-size models, column generation, constraint separation
- Graph problems, examples of real-life applications, optimization software tools
Readings/Bibliography
Slides on virtuale.unibo.it (at the web page of the course)
Further readings:
Fischetti M. Introduction to Mathematical Optimization. Kindle Direct Publishing, 2019.
Christos H. Papadimitriou and Ken Steiglitz, Combinatorial optimization: algorithms and complexity. Dover, 1998.
D. Bertsimas and J. Tsitsiklis, Introduction to linear programming. Dynamic Ideas and Athena Scientific, Belmont, Massachusetts, 2008.
D. Bertsimas, D. and R. Weismantel, Optimization over integers. Dynamic Ideas, Belmont, Massachusetts, 2005.
Teaching methods
The course consists of lectures and class exercises.
Assessment methods
The exam consists of a written exam in which some exercises on topics of the course have to be solved (about 60 minutes). On the day after the written exam, an oral exam covering all topics of the course (including theorems and proofs) completes the exam.
Written and oral exams must be done in the same exam round.
Teaching tools
Slides on virtuale.unibo.it (at the web page of the course) and optimization software tools.
Office hours
See the website of Valentina Cacchiani
SDGs
This teaching activity contributes to the achievement of the Sustainable Development Goals of the UN 2030 Agenda.