DALMINE
Overview
Date/time interval
Syllabus
Course Objectives
This course provides a rigorous introduction to the theory and applications of linear, discrete and stochastic programming to engineering. In terms of theory, the student will learn the structural properties and state-of-the-art solution algorithms to solve decision problems. From a practical viewpoint, the student will learn how to model real-world problems as optimization models and how to interpret their solutions computed via commercial package programs.
Topics covered include the simplex method, duality in linear programming, sensitivity analysis, network-type problems, integer programming, stochastic programming and dynamic programming.
In terms of applications, decision problems from widely different contexts are considered: manufacturing industry, transportation, finance, health, energy, network models. At the end of the course the student will be also able to realize simple GAMS coding for solving the considered decision problems.
At the end of the course the student will be able to:
- Understand the conceptual approach of Operations Research as a tool to formulate, solve and evaluate decision problems relating to complex systems.
- Understand the structural properties and state-of-the-art solution algorithms to solve decision problems.
- Model real-world problems as optimization models.
- Interpret the solution computed via commercial package programs and provide its economic interpretation.
- Implement a mathematical model in the GAMS environment.
Course Prerequisites
Real functions of real variables. Matrix algebra. Systems of linear equations.
Teaching Methods
The course will consist of lectures based on traditional teaching including theory, exercises and tutoring. Some of the lectures will be based on exercise sessions in GAMS using PC-labs.
Assessment Methods
The final exam is based on a written test followed by an oral interview. The written test is composed of exercises, one of which based on modeling and implementing under GAMS environment a real case problem. The oral exam is aimed at assessing the knowledge of the theory covered by the course.
Contents
- Introduction to Operational Research
- Linear (integer) programming models for real case applications: Blending of products, assignment of machining operations, the transportation problem, the diet problem, the assignment problem, the scheduling problem. Examples.
- Linear programming (LP)
- Formulations and equivalent forms.
- Geometry of linear programming: vertices and basic solutions.
- Simplex method.
- Duality in linear programming and economic interpretation.
- The dual simplex method.
- Sensitivity analysis and post-optimality in linear programming.
- Integer linear programming
- Theory of linear integer programming.
- Total unimodularity (UM and TUM).
- Branch and bound algorithm.
- Gomory cuts.
- The knapsack problem and algorithms.
- The transportation and assignment problems.
- Graph theory
- Minimum spanning trees and Prim’s algorithm.
- Shortest path problem and Dijkstra’s algorithm.
- Max flow problem and Ford-Fulckerson’s algorithm.
- The traveling salesman problem.
- Introduction to dynamic programming.
- Introduction to stochastic programming and applications.
Online Resources
More information
The course material will be provided by means of the e-learning platform of the University of Bergamo.
If the teaching activity will be mixed or in remote mode, changes can be done compared to what stated in the syllabus, to make the course and the exams available also in these modalities.
For more details write to: francesca.maggioni@unibg.it