Faculty: Science and Technology

Course: Optimization and Operational Research

Programme: Study Abroad in Engineering

Semester: 2 – Spring

ECTS credits: 3

Duration: 22.5 hours

Language of instruction: English

Instructor: Jordi Villà-Freixa

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, among others, 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.

Attendance policy

Attendance is mandatory for all classes. Any presentation or activity missed due to student absences can only be rescheduled in cases of certified medical or family emergencies. If a student misses more than three classes in any course half a letter grade will be deducted from the final grade for each additional absence. Seven absences in any course will result in a Fail grade. Notice that there is a minimum of 80% attendance.

Learning outcomes

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

  • identify specific problems of linear programming;
  • identify and use techniques to solve an optimization or linear programming problem;
  • 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.

Required work and assessment methods

Throughout the course there will be two evaluation methods, the programming exercises to be delivered and a series of Quiz in the Moodle platform. The percentage corresponding to each of these evaluation methods is:

  • Quizes (30%): in-class quizes along the course.
  • Programming exercises to be delivered (70%).

Contents

Unit 1: Introduction to OR and Optimization

  • Week 1 (7/02). Introduction to Operations Research.

    • Introduction to systems modelling; optimality and practicality
    • Introduction to the Python/colab environment; GitHub
  • Weeks 2-4 (14-28/02). Non-linear optimization.

    • Concepts and algorithms in non-linear optimization
    • Unconstrained optimization
    • Constrained optimization (Lagrange multiplier theorem, Kuhn-Tucker multiplier theorem)

Unit 2: Linear programming

  • Weeks 5-6 (7-21/03). The linear programming model

    • Fundamental principles of linear programming
    • Geometric resolution
    • Basic mathematics tools
  • Weeks 7-8 (28/03-18/04). The Simplex method

    • Standard form,
    • Deviation variables
    • Basic feasible solutions
    • Artificial variables
  • Weeks 9-10 (25/04-2/05). Duality

    • Primal and dual problems, economic interpretation, conditions of optimality, resolution of the dual by the primal and penalty method

Unit 3: Sensitivity analysis

  • Weeks 11 (9/05). Sensitivity Analysis

    • Sensitivity analysis: the effect of modifying the objective function or the constraints

Unit 4: Network analysis

  • Weeks 12-13 (16-23/05). Network analysis

    • Graphs and Networks
    • Maximum flow / minimal cost
    • Network connectivity
    • Shortest path problems
    • Dynamic programming
    • Project management

Unit 5: Integer programming

  • Week 14 (30/05). Integer programming

    • Branch and bound
    • Cutting planes
    • Cover inequalities
    • Lagrangian relaxation
    • Column generation

Requirements to pass the course. Exam retake

To pass the course, students should obtain at least an overall average grade of 5 out 10, with the following conditions:

  • At least an average grade of 4 out 10 in tests. Otherwise, a final test will be conducted to retake the grade for this part of the subject, with a maximum grade of 8 out 10.
  • At least a grade of 5 in programming exercises. If delivery is delayed, the grade will be penalized with a maximum score of 60%.

Code

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).