Operations Research

About the course: The course will introduce some methods and algorithms from different sub-fields of OR. Each week, we will jump into very different topics such as linear programming, network optimization models, job scheduling, heuristics, and more.

Prerequisites:

  • Python 3.8
  • Jupyter notebook; required libraries: matplotlib, numpy, graphviz, torch
  • It is suggested to use own laptops
  • Your scripts will be evaluated during the laboratories. However, you are also asked to send them via e-mail (converted to HTML!, see nbcovert function). Please, begin e-mail titles with “[OR].”

Grading (labs): link

Assign to the course here: link to google spreadsheet

Calendar: pdf

Marks: google spreadsheet

Hints for the exam: pdf

Materials:

NOTOPIC
1Linear programming
Keywords: formulating optimization problems using LP, solving LP problems using graphical method.

Files for lab: bundle
Files for lecture: bundle
2The Simplex Algorithm
Keywords: the augmented form of the LP problem, the simplex algorithm, the big M method, other constraint forms.

Files for lab: bundle
Files for lecture: bundle
3The Matrix Form and The Duality Theory
Keywords: the fundamental insight, the dual problem, primal-dual relations.

Files for lab: bundle
Files for lecture: bundle
4Sensitivity Analysis
Keywords: the sensitivity analysis, dual simplex method.

Files for lab: bundle
Files for lecture: bundle
5The Transportation and the Assignment problem
Keywords: The transportation simplex algorithm, the hungarian algorithm.

Files for lab: bundle
Files for lecture: bundle
6Network Optimization Models
Keywords: The shortest path problem, the minimum spanning tree problem, the maximum flow problem, the minimum cost flow problem.

Files for lab: bundle
Files for lecture: bundle
7Dynamic Programming
Keywords: The deterministic dynamic programming, probabilistic dynamic programming.

Files for lab: bundle
Files for lecture: bundle
8Integer Programming
Keywords: Branch and Bound algorithms for pure binary integer programming problems and mixed integer programming problems.

Files for lab: bundle
Files for lecture: bundle
9Nonlinear programming
Keywords: Convexity/concavity, bi-section algorithm, Newton’s methods for finding roots/maxima, HHT conditions, quadratic programming.

Files for lab: bundle
Files for lecture: bundle
10Metaheuristics
Keywords: The local improvement method, tabu search, simulated annealing, particle swarm optimization, evolutionary algorithms.

Files for lab: bundle
Files for lecture: bundle
11Job Scheduling
Keywords: Problem classes, optimization criteria, McNaughton’s algorithm, Hu’s algorithm, Coffman-Graham algorithm, Johnson’s algorithm, Gonzalez-Sahni algorithm.

Files for lab: bundle
Files for lecture: bundle
12Queueing Theory
Keywords: Basic queueing system, quantities and relationships, exponential distribution, the birth-and-death process, MMs model, application of queueing theory.

Files for lab: bundle
Files for lecture: bundle