73414 - Algorithms for Decision Making M

Learning outcomes

The course introduces mathematical models for optimization problems arising in many branches of engineering, industry and complex systems. General solution methods and software tools (commercial and freeware) are presented.

Course contents

Requirements/Prior knowledge

A good knowledge of linear algebra and basic mathematics is required.  

All lectures and tutorials will be in English.

 

Course Contents

The course is provided with a first part in which the basic concepts of Linear and Integer Programming are briefly discussed. In particular:

• linear programming and duality theory;
• integer linear programming and branch-and-bound complexity of the algorithms;
• basics of graphs theory.

The second part of the course is on modeling and solution methods. We will start from integer linear programming models for basic combinatorial optimization problems with special emphasis on the discussion of the quality of their continuous relaxation. We will discuss solution methods for problems of exponential size.

Some complex applications involving models with huge number of variables and/or constraints will be discussed.

• Service design;
• Routing;
• Cutting and packing;
• ...

Readings/Bibliography

• Jon Lee - A First Course in Linear Optimization (free!) https://sites.google.com/site/jonleewebpage/home/publications#book
• Silvano Martello - Ricerca Operativa per la Laurea Magistrale
• Dimitris Bertsimas, John Tsitsiklis - Introduction to Linear Optimization
• The AMPL book http://ampl.com/resources/the-ampl-book/

Teaching methods

• Lectures (blackboard);
• Exercises to be solve at home and later discussed in class;

Assessment methods

Written and oral exam, the same day:

• written exercise (about 1.5 hour, open book), written “theory” question (15 minutes);
• discussion of the exercise, oral assessment.

After the written exam, a grade will be assigned. The students can decline this grade. Those who decide to go for the oral assessment will receive a final grade that will be recorded (the final grade cannot be declined).

Higher grades will be awarded to students who demonstrate an organic understanding of the subject, a high ability for critical application of the models/methodologies to new examples, and a clear and concise presentation of the theory.

To obtain a passing grade, students are required to at least demonstrate a knowledge of the key concepts of the subject, some ability for critical application of the models/methodologies to new examples.

A failing grade will be awarded if the student shows knowledge gaps in key-concepts of the subject, and insufficient ability for critical application of the models/methodologies to new examples.

Teaching tools

Some lecture notes in English will be provided.

Office hours

See the website of Enrico Malaguti