Operations Research
A.Y. 2023/2024
Learning objectives
The course aims to introduce Operations Research, i.e. the scientific study of methods for solving complex decision problems with the help of a computer. The aim is to learn to construct mathematical models of optimization problems, knowing how to classify models and to know the mathematical foundations of algorithmic techniques that allow them to be solved.
Expected learning outcomes
Students will develop the ability of recognizing optimization problems, formulating them in mathematical models and they will know the mathematical properties that underlie the algorithms developed to solve them.
Lesson period: Second semester
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course can be attended as a single course.
Course syllabus and organization
Single session
Responsible
Lesson period
Second semester
Course syllabus
INTRODUCTION:
· Introduction to Operations Research. Origins, applications, relations with other disciplines.
· Mathematical models. Data, variables, constraints, objective functions, decision-makers.
LINEAR PROGRAMMING (LP):
· Applications. Examples of linear programming problems.
· Definitions and properties. General form ol LP problems; inequalities form with its geometrical interpretation; standard form. Base solutions and fundamental theorem of LP.
· Duality. Farkas lemma. Weak and strong duality theorems. Complementary slackness theorem. Economic interpretation of LP.
· Algorithms. Canonical forms. Primal and dual simplex algorithms.
· Revised simplex algorithm.
· Post-optimal analysis. Sensitivity analysis and parametric analysis.
MULTI-OBJECTIVE PROGRAMMING (MOP):
· Applications. Examples of multi-objective programming problems.
· Definitions and properties. Dominance, Pareto solutions, Pareto-optimal set, utopistic solution.
· Algorithms for finding the Pareto set. Weigths method. Constraints method.
Geometric interpretation. Solution of linear programming exercises with two objectives via parametric analysis.
· Criteria for the choice of a solution. Standards criterion, indifference curves criterion, utopistic solution criterion.
INTEGER LINEAR PROGRAMMING (ILP):
· Applications. Examples of integer linear programming and combinatorial optimization problems.
Use of binary variables for modeling logical conditions.
· Definitions and properties. Linear relaxation, integrality gap. Other types of relaxation.
· Algorithms. Branch-and-bound.
NON-LINEAR PROGRAMMING (NLP):
· Applications. Examples of non-linear programming problems.
· Definitions and properties. Gradient vector, Hessian matrix. Convexity and convex programming. KKT conditions for constrained non-linear programming.
· Algorithms. Algorithms for mono-dimensional optimization. Iterative methods, gradient algorithm.
· Introduction to Operations Research. Origins, applications, relations with other disciplines.
· Mathematical models. Data, variables, constraints, objective functions, decision-makers.
LINEAR PROGRAMMING (LP):
· Applications. Examples of linear programming problems.
· Definitions and properties. General form ol LP problems; inequalities form with its geometrical interpretation; standard form. Base solutions and fundamental theorem of LP.
· Duality. Farkas lemma. Weak and strong duality theorems. Complementary slackness theorem. Economic interpretation of LP.
· Algorithms. Canonical forms. Primal and dual simplex algorithms.
· Revised simplex algorithm.
· Post-optimal analysis. Sensitivity analysis and parametric analysis.
MULTI-OBJECTIVE PROGRAMMING (MOP):
· Applications. Examples of multi-objective programming problems.
· Definitions and properties. Dominance, Pareto solutions, Pareto-optimal set, utopistic solution.
· Algorithms for finding the Pareto set. Weigths method. Constraints method.
Geometric interpretation. Solution of linear programming exercises with two objectives via parametric analysis.
· Criteria for the choice of a solution. Standards criterion, indifference curves criterion, utopistic solution criterion.
INTEGER LINEAR PROGRAMMING (ILP):
· Applications. Examples of integer linear programming and combinatorial optimization problems.
Use of binary variables for modeling logical conditions.
· Definitions and properties. Linear relaxation, integrality gap. Other types of relaxation.
· Algorithms. Branch-and-bound.
NON-LINEAR PROGRAMMING (NLP):
· Applications. Examples of non-linear programming problems.
· Definitions and properties. Gradient vector, Hessian matrix. Convexity and convex programming. KKT conditions for constrained non-linear programming.
· Algorithms. Algorithms for mono-dimensional optimization. Iterative methods, gradient algorithm.
Prerequisites for admission
Linear algebra
Teaching methods
The course takes place through lectures and practical exercises. It is warmly recommended to attend the lectures and above all the practical sessions.
Teaching Resources
Hillier and Liebermann,
Introduction to Operations Research
Introduction to Operations Research
Assessment methods and Criteria
The exam consists of two tests: one at the PC and an oral one.
In the lab exam (3 hours) some exercises are proposed; students are required to write the mathematicl model of an optimization problem described in natural language, to solve it with a math programming solver and to correctly interpret its output answering some questions. The outcome is a range (6/30) for the final mark. It is communicated on the course webpage. The oral exam encompasses the whole content of the course.
In the lab exam (3 hours) some exercises are proposed; students are required to write the mathematicl model of an optimization problem described in natural language, to solve it with a math programming solver and to correctly interpret its output answering some questions. The outcome is a range (6/30) for the final mark. It is communicated on the course webpage. The oral exam encompasses the whole content of the course.
Educational website(s)
Professor(s)