2020/2021

2020/2021

DM270

MAT/09 (OPERATIONAL RESEARCH)

DEPARTMENT OF MATHEMATICS "FELICE CASORATI"

MATHEMATICS

PERCORSO COMUNE

1°

2nd semester (01/03/2021 - 11/06/2021)

6

56 lesson hours

English

ORAL TEST

GUALANDI STEFANO (titolare) - 6 ECTS

This course is an applied math course, dedicated to math and engineering students. The students of this course should have followed the fundamental courses in programming, analysis, and linear algebra.

The course is a comprehensive introduction to the theory, models, and algorithms of mathematical optimization. The goals of this course are the following:

1. To present students with knowledge of the state-of-the-art in the theory and practice of solving optimization problems.

2. To help each student develop his or her own intuition about modeling and solving large scale real-world problems using optimization software.

- Part I: Optimization Modeling

Optimization modeling is the skill of reducing a messy computational or engineering problem to a mathematical form that can be solved by using optimization software. By recognizing mathematical patterns in real-world problems, students will develop an intuition for which problems are solvable using optimization modeling techniques and gain the knowledge and skills to then solve them.

- Part II: Network flows

Network flow problems form a subclass of linear programming problems with several applications. This part of the course will focus on key special cases of network flow problems including the following: the shortest path problem, the maximum flow problem, the minimum cost flow problem.

- Part III: Linear Optimization
The topics in linear optimization include: The Simplex Method, Duality Theory, Sensitivity Analysis, Interior-Point Methods, Implementation Issues.

- Part IV: Integer Optimization
The topics in integer optimization include: Branch and Bound, Cutting Plane Algorithms, Strong Valid Inequalities, Lagrangian Duality, Column Generation Algorithms, Heuristic Algorithms.

Lectures and Laboratories in Computer Labs.

Lecture notes available on the web page of the course.


Selected chapters from:
• H.P. Williams. Model building in mathematical programming. John Wiley & Sons, 2013.
• R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows, 1988.
• D. Bertsimas and J. N. Tsitsiklis. Introduction to Linear Optimization, Athena Scientific, 1997.
• D. Bertsimas and R. Weismantel. Optimization over Integers. Belmont, MA: Dynamic Ideas, 2005.

Oral exam + Project Report

The course is organized in four parts. During each part, we will use as running examples, large-scale optimization problems currently solved in Computational Biology (e.g., Alignment of Genomic Sequencing, Metabolic Networks, Haplotype Analysis), Transportation Planning and Scheduling (Home Health Care Routing, Nurse Scheduling), and Machine Learning (e.g., Regression, Clustering, Optimal Classification Trees).