Optimization & Operations Research

Overview

Instructor: Florian Dahms, R 1-138

  • Lecture: Thursday 10:00-11:30 (5-101)
  • Exercise: Tuesday 10:00-11:30 (1-312)
  • OLAT Link
  • Exercise tasks in Jupyter
  • Panopto
  • Written exam

References

  • "Theory of Linear and Integer Programming", A. Schrijver

This course is about methods with which we can solve difficult problems optimally.

    Applications:

  • Routes for truck fleets
  • Site selection for factories
  • Production plans
  • Timetables
  • Staff schedules
  • Poker strategy

Prerequisites

  • Linear Algebra
  • Programming basics

Vectors

\[ a = \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix} \in \mathbb{R}^3 \]

\[ a^T = \begin{bmatrix} 1 & 2 & 3 \end{bmatrix} \]

Dot product

\[ a = \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix} \quad b = \begin{bmatrix} 4 \\ 5 \\ 6 \end{bmatrix} \]

\[ a \cdot b = a^T b = 1 \cdot 4 + 2 \cdot 5 + 3 \cdot 6 = 32 \]

Matrices

\[ A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} \in \mathbb{R}^{2 \times 3} \]

\[ A^T = \begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{bmatrix} \in \mathbb{R}^{3 \times 2} \]

Matrix-vector product

\[ A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} \quad b = \begin{bmatrix} 7 \\ 8 \\ 9 \end{bmatrix} \]

\[ A b = \begin{bmatrix} 1\cdot 7 + 2 \cdot 8 + 3 \cdot 9 \\ 4 \cdot 7 + 5 \cdot 8 + 6 \cdot 9 \end{bmatrix} = \begin{bmatrix} 50 \\ 122 \end{bmatrix} \]

Matrix-matrix product

\[ A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} \in \mathbb{R}^{2 \times 3} \quad B = \begin{bmatrix} 7 & 10 \\ 8 & 11 \\ 9 & 12 \end{bmatrix} \in \mathbb{R}^{3 \times 2} \]

\[ A B = \begin{bmatrix} 1\cdot 7 + 2 \cdot 8 + 3 \cdot 9 & 1 \cdot 10 + 2 \cdot 11 + 3 \cdot 12 \\ 4 \cdot 7 + 5 \cdot 8 + 6 \cdot 9 & 4 \cdot 10 + 5 \cdot 11 + 6 \cdot 12 \end{bmatrix} \\= \begin{bmatrix} 50 & 68 \\ 122 & 167 \end{bmatrix} \in \mathbb{R}^{2 \times 2} \]

It holds that \((A B)^T = B^T A^T\)

History

In the 1st World War, Britain optimized their fleet deployment with mathematical methods to minimize losses due to German submarines.

In the 2nd World War, "Operations Research" became its own discipline with about 1000 people employed in Britain.

  • Positioning and deployment of the new radar system
  • Coordination of anti-aircraft guns
  • Coordination of bomber squadrons
  • Optimization of production chains
  • ...

After the 2nd World War, many of the new approaches were pursued further in the industry.

  • Petrochemicals
  • Airlines
  • Logistics
  • Finance

Python

  • One of the most popular programming languages.
  • (Relatively) easy to learn.
  • Excellent libraries for data science and machine learning.
  • Open source
  • I use it in the majority of my courses.
Link Jupyter

More Python References

Within the context of the lecture, we primarily use 3 libraries:

Local Python / Jupyter Installation:
Anaconda

In the lecture, we continuously switch between mathematical notation and Python code

$$\sum_{i=1}^n i x_i$$ 

            sum(i * x[i] for i in range(1, n + 1))

Note: Mathematicians start arrays at 1,
Computer Scientists at 0

$$\sum_{i=1}^n i x_i$$ 

            sum((i+1) * x[i] for i in range(n))

Exercises in Jupyter

If you achieve more than 50% of the exercise points, you will receive a 0.3 grade point bonus on the exam.