CloseHelpPrint
Kies de Nederlandse taal
Course module: 201800003
201800003
Operations Research Techniques 1
Course info
Course module201800003
Credits (ECTS)5
Course typeCourse
Language of instructionEnglish
Contact persondr.ir. E.A. Lalla
E-maile.a.lalla@utwente.nl
Lecturer(s)
PreviousNext 2
Lecturer
dr. D. Demirtas
Examiner
dr.ir. E.A. Lalla
Contactperson for the course
dr.ir. E.A. Lalla
Lecturer
dr.ir. A.G. Leeftink
Lecturer
dr.ir. J.M.J. Schutten
Academic year2022
Starting block
1A/  2A
RemarksContact person 1A: Lalla, E.A. (M7666019)
Contact person 2A: Maan-Leeftink, A.G
Application procedureYou apply via OSIRIS Student
Registration using OSIRISYes
Aims

Aim of the course is to familiarize students with formulating and solving combinatorial optimization (and especially integer linear programming) problems. Students get acquainted with exact solutions methods as well as heuristics.
At the end of the course a student
  • is able to formulate an appropriate ILP model for a given problem context;
  • understands the simplex method and the concept of duality and is able to determine the dual of an LP problem;
  • can solve an ILP model using an appropriate solver (e.g. AIMMS) and interpret the outcomes; [PRACTICAL]
  • can apply the branch-and-bound method (including Balas’ and Dakin’s method) to find the optimal solution to an ILP problem;
  • is familiar with the complexity of combinatorial optimization (C.O.) problems and is able to discuss whether P = NP;
  • can apply a number of constructive and local search (meta)heuristics to solve C.O. problems and is able to determine the algorithm run length;
  • is able to implement a heuristic for a C.O. problem in Delphi. [PRACTICAL]
  • understands the idea behind deterministic dynamic programming (DP) and can apply DP to solve typical C.O.problems.
 
 
Content

Many problems from the field of operations management can only be modeled and solved as a combinatorial optimization problem. Solving such problems is generally far from trivial. For many of these problems, algorithms for finding the solution have a computation time that grows exponentially with the problem size. In practice, obtaining optimal solutions is often not necessary; an approximation solution that can be obtained in little time may even be more useful. This course deals with formulating mathematical models and solving them. For the most part it focuses on various exact and approximation methods / algorithms, and their application in well-known problems that originate from the practice of operations management and logistics. Besides, attention is being paid to complexity and algorithm run time.
Overview of the course contents
  • Mathematical programming / model formulation;
  • Simplex method, duality and economic interpretation of LP optimization results;
  • Branch-and-bound (Knapsack, Dakin's algorithm, Balas);
  • Local Search (r/Or-opt, tabu search, steepest descent, simulated annealing);
  • Meta heuristics;
  • Constructive heuristics;
  • Computation time, worst-case analysis;
  • Complexity Theory;
  • Dynamic programming
This course is given twice a year (in Quartiles 1A and 2A) and should be followed (after or) in conjunction with IEM RO, because in IEM RO the programming language Delphi is discussed that is needed to program some of the heuristics discussed in this course.

 
Assumed previous knowledge
Assumed knowledge
1) The student should be familiar with formulating LP (linear programming) models.
2) If a student does not take the IEM RO course at the same time (or has taken this course earlier) the student should contact Gréanne Maan-Leeftink (a.g.leeftink@utwente.nl) before the course starts to check if he or she masters a programming language sufficiently to finish the course successfully.
Participating study
Master Industrial Engineering and Management
Required materials
Book
David J. Rader jr, Deterministic Operations Research: Models and Methods in Linear Optimization, Wiley, 2010, ISBN 9780470484517
Articles
Additional materials (made available via Canvas)
Book
W.L. Winston, Operations Research: Applications and Algorithms (4th ed.), Cengage, ISBN 9780534380588
Recommended materials
-
Instructional modes
Lecture

Practical

Self study without assistance

Tutorial

Tests
Exam

CloseHelpPrint
Kies de Nederlandse taal