00884 - Operations Research

Learning outcomes

At the end of the course the student is expected to master the main theoretical and algorithmic tools to formulate and solve mathematical models for three classes of optimization problems: (continuous) Linear Programming (LP), Network Flow problems, and some combinatorial problems on graphs.

Course contents

The course introduces the fundamental tools for the construction and solution of analytical optimization models for management and resource allocation problems, with applications in many fields of science and engineering and economic activities (logistics, transport, telecommunications, finance, energy, health, etc).

The concept of LP formulation for an optimization problem, its properties and techniques to solve it will be developed first. Then, network flow problems and some combinatorial problems on graphs (with related properties and algorithms) will be presented, through which it is possible to abstract and model optimization problems for resource allocation and process management.

• Introduction to mathemtical optimization and LP formulations
• Linear pogramming
  • Elements of convex optimization
  • Geometry and algebra of linear programming (LP): properties of polyhedra, bases and basic solutions, level curve method
  • Fundamental theorem of LP and duality theory
  • Simplex algorithm (primal and dual)
  • Sensitivity analysis
    
• Graphs and network flows
  
  • Mathematical models for problems on graphs and networks
  • Unimodularity conditions
  • Trees, paths and cuts, visits of graphs and trees
  • Shortest path problem
  • Maximum flow problem
  • Minimum cost flow problem
  • Minimum cost spanning tree problem
  • Matching and assignment problems
    
• (a brief) Introduction to Integer Linear Programming

Readings/Bibliography

• Jon Lee "A First Course in Linear Optimization"
• Fabio Schoen "Optimization Models"
• R.K. Ahuja, T.L. Magnanti, J. Orlin "Network flows. Theory, algorithms and applications"
• F.S. Hillier, G.J. Lieberman "Introduction to Operations Research"
• Matteo Fischetti "Lezioni di Ricerca Operativa"

Teaching methods

Frontal lessons and exercise sessions.

Assessment methods

The student will be assessed on his/her ability to model and formulate optimization problems in terms of LP, or by abstracting problems on graphs and flow networks. Knowledge of the theoretical properties and algorithms for these classes of problems will also be verified.

The exam consists of a written test and an oral test that must be taken within the same session. In the case of an "insufficient" grade in the written test, the student will have to repeat the written test in another session. In the case of an evaluation of at least "sufficient", the student will proceed to the oral test. The oral test is aimed at verifying the knowledge of the topics covered in class. The final grade takes into account the results achieved in both tests.

It is compulsory to sign up for the exam (both for the written and the oral exams) using AlmaEsami and, in case one is not able to take the exam, it is compulsory to remove one's name from the same list.

Teaching tools

The teaching material (slides, notes, exercises) will be available on the University of Bologna e-learning platform (https://virtuale.unibo.it ).

Office hours

See the website of Laura Galli