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