Notes on the Study Abroad course on Operational Research (Vic, February-June 2022)

Course Description

In this course we will deal with Operations Research (OR), a scientific discipline at the interface
of Applied Mathematics, Computer Science and Engineering, defined as the use of quantitative
methods to assist analysts and decision-makers in designing, analyzing, and improving the
performance or operation of systems. OR can be used in financial systems, scientific or
engineering systems, or industrial systems. Its aim is to rationalize, simulate, optimize, model
and plan the architecture and operation of complex systems that are increasingly present in
industry and large organizations. We will focus on the optimization problem, and we will be
using a fully practical approach, using Python/iPython, Colab and libraries like google OR as our
main tools during the course to demonstrate and test what we learn from the theoretical
sessions.

Prerequisites

Linear algebra, matrix analysis, basic numerical analysis, differential, and integral calculus. Basic
knowledge of programming Python.

Learning outcomes

By the end of the course, students should be able to:

  • To identify and solve the specific problems of linear programming.
  • To identify and use techniques to solve an optimization or linear programming problem.
  • To be able to implement specific OR algorithms

Method of presentation

Lectures and practical training:

  • Short lectures with appropriate visual support provide the theoretical content of the
    sessions.
  • Practical training will present specific problems to be solved using computational tools
    and algorithms in and out of the class.

Contents

Unit 1: Introduction to OR and Optimization

  • Week 1. Introduction to Operations Research.
    • Introduction to systems modelling; optimality and practicality
    • Introduction to the Python/colab environment; GitHub
    • Q1. Introduction Quiz.
  • Weeks 2-3. Non-linear optimization
    • Concepts and algorithms in non-linear optimization
    • Unconstrained optimization
    • Constrained optimization (Lagrange multiplier theorem, Kuhn-Tucker multiplier
      theorem)
    • Exercise to deliver 1
    • Q2. Non-Linear Quiz.
    • E1. NLO program

Unit 2: Linear programming

  • Weeks 4-5. The linear programming model
    • Fundamental principles of linear programming
    • Geometric resolution
    • Basic mathematics tools
    • Q3. LP Quiz.
  • Weeks 6. The Simplex method
    • Standard form,
    • Deviation variables
    • Basic feasible solutions
    • Artificial variables
    • Q4. Simplex Quiz.
    • E2. LP program
  • Week 7. Duality
    • Primal and dual problems, economic interpretation, conditions of optimality, resolution of the dual by the primal and penalty method
    • Q5. Duality Quiz

Unit 3: Sensitivity analysis and optimal experimental design

  • Week 8. Sensitivity Analysis
    • Sensitivity analysis: the effect of modifying the objective function or the constraints
    • Q6. Sensitivity Analysis Quiz.
  • Week 9. Optimal Experimental Design
    • D-criterion, I-criterion
    • Fraction of design space plots
    • Multiplicative algorithm
    • Exact designs
    • Q7. OED Quiz.
    • E3. SA/OED program

Unit 4: Network analysis and Integer programming

  • Week 10. Network analysis
    • Graphs and Networks
    • Maximum flow / minimal cost
    • Network connectivity
    • Shortest path problems
    • Dynamic programming
    • Project management
    • E4. Network analysis program
  • Week 11. Integer programming
    • Branch and bound
    • Cutting planes
    • Cover inequalities
    • Lagrangian relaxation
    • Column generation
    • Q8. Integer programming Quiz.

Unit 5. Stochasticity and simulation

  • Week 12-13. Markov processes
    • State transitions
    • State probabilities
    • First passage probabilities
    • Steady-state analysis
    • Hidden Markov models
    • Other related topics (queuing systems)
    • Q9. Markov processes Quiz.
    • E5. Stochastic simulation program
  • Week 14-15. Simulation
    • Discrete simulation processes
    • Q10. Simulations Quiz

Recommended reading

  1. “Operations research. A practical Introduction (2nd Ed)” by Michael W. Carter, Camile C. Price
    and Ghaith Rabadi. CRC Press
  2. “A guide to simulation (2nd Ed)” by Paul Bratley, Bennett L. Fox and Linus E. Schrage
  3. “Numerical Optimization (2nd Ed)” by Jorge Nocedal and Stephen J. Wright

Python tools for Operational Research

We will be using Google-OR tools for Python:

  1. Option 1: Working locally in your computer. You have several ways to run Python:
  2. Option 2: Working in the cloud. The most immediate choice is google colab (there are other alternatives like Jupyterlite). Open a google account and go to colab.

GitHub repository

The code employed through the course can be found in the ORCode Github repository. The repository contains code developed on purpose for the course, as well as a bunch of other code adapted from nice job made by other developers (stated and referenced accordingly when needed).