97271 - Mathematical Programming

Academic Year 2022/2023

Learning outcomes

At the end of the course the student knows the main theoretical and algorithmic methods of mathematical programming for the solution of optimization problems and decision support; is able to analyse an optimization problem and develop the appropriate mathematical model for its resolution. The course includes the illustration of real world applications and laboratory experiences which shows how to implement an algorithm based on a mathematical programming model and how to use the main available solvers.

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. After the written exam, the list of students that are admitted to the oral exam is provided. There is a unique mark after the oral exam.

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