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
  
  • 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)
    
• Graphs and network flows
  
  • Mathematical models for problems on graphs and networks
    
  • 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

Readings/Bibliography

• J. Lee "A First Course in Linear Optimization"
• F. 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"
  

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.

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.

Students with SLDs or temporary or permanent disabilities: it is recommended that they contact the relevant University office in good time (https://site.unibo.it/studenti-con-disabilita-e-dsa/it ). The office will propose any possible accommodations to the students concerned; these must in any case be submitted, at least 15 days in advance, to the approval of the course instructor, who will assess their appropriateness also in relation to the learning objectives of the course.

As regards assessment of learning, the use of AI is prohibited. Any use constitutes a violation of academic integrity.

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