SluitenHelpPrint
Switch to English
Cursus: 201800003
201800003
Operations Research Techniques 1
Cursus informatie
Cursus201800003
Studiepunten (ECTS)5
CursustypeCursus
VoertaalEngels
Contactpersoondr.ir. E.A. Lalla
E-maile.a.lalla@utwente.nl
Docenten
VorigeVolgende 2
Docent
dr. D. Demirtas
Docent
dr.ir. E.A. Lalla
Contactpersoon van de cursus
dr.ir. E.A. Lalla
Docent
dr.ir. A.G. Leeftink
Docent
dr.ir. J.M.J. Schutten
Collegejaar2021
Aanvangsblok
1A/  2A
OpmerkingContact person 1A: Lalla, E.A. (M7666019)
Contact person 2A: Maan-Leeftink, A.G
AanmeldingsprocedureZelf aanmelden via OSIRIS Student
Inschrijven via OSIRISJa
Cursusdoelen

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

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.

 
Voorkennis
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
Verplicht materiaal
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
Aanbevolen materiaal
-
Werkvormen
Hoorcollege

Practicum

Werkcollege

Zelfstudie geen begeleiding

Toetsen
Exam

SluitenHelpPrint
Switch to English