About the course: The course will introduce some ideas 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
Marks: google spreadsheet (can be found at eKursy)
Hints for the exam: pdf
Topics (materials can be found at eKursy):
NO | TOPIC |
1 | Linear programming Keywords: formulating optimization problems using LP, solving LP problems using graphical method. |
2 | The Simplex Algorithm Keywords: the augmented form of the LP problem, the simplex algorithm, the big M method, other constraint forms. |
3 | The Matrix Form and The Duality Theory Keywords: the fundamental insight, the dual problem, primal-dual relations. |
4 | Sensitivity Analysis Keywords: the sensitivity analysis, dual simplex method. |
5 | The Transportation and the Assignment problem Keywords: The transportation simplex algorithm, the hungarian algorithm. |
6 | Network Optimization Models Keywords: The shortest path problem, the minimum spanning tree problem, the maximum flow problem, the minimum cost flow problem. |
7 | Dynamic Programming Keywords: The deterministic dynamic programming, probabilistic dynamic programming. |
8 | Integer Programming Keywords: Branch and Bound algorithms for pure binary integer programming problems and mixed integer programming problems. |
9 | Nonlinear programming Keywords: Convexity/concavity, bi-section algorithm, Newton’s methods for finding roots/maxima, HHT conditions, quadratic programming. |
10 | Metaheuristics Keywords: The local improvement method, tabu search, simulated annealing, particle swarm optimization, evolutionary algorithms. |
11 | Job Scheduling Keywords: Problem classes, optimization criteria, McNaughton’s algorithm, Hu’s algorithm, Coffman-Graham algorithm, Johnson’s algorithm, Gonzalez-Sahni algorithm. |
12 | Queueing Theory Keywords: Basic queueing system, quantities and relationships, exponential distribution, the birth-and-death process, MMs model, application of queueing theory. |