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



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 wellknown 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;
 Branchandbound (Knapsack, Dakin's algorithm, Balas);
 Local Search (r/Oropt, tabu search, steepest descent, simulated annealing);
 Meta heuristics;
 Constructive heuristics;
 Computation time, worstcase 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 knowledgeAssumed 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 MaanLeeftink (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. 
Master Industrial Engineering and Management 
  Required materialsBookDavid J. Rader jr, Deterministic Operations Research: Models and Methods in Linear Optimization, Wiley, 2010, ISBN 9780470484517 
 ArticlesAdditional materials (made available via Canvas) 
 BookW.L. Winston, Operations Research: Applications and Algorithms (4th ed.), Cengage, ISBN 9780534380588 

 Recommended materialsInstructional modesLecture
 Practical
 Self study without assistance
 Tutorial

 TestsExam


 