4EK605 Combinatorial Optimization

Aims of the course:

The aim of the course is to make students acquainted with modeling of the operations research problems with the use of discrete variables (integer and binary). Elementary and advanced models and methods are used for solution. Students will work with special optimization system for solving discrete problems (MPL for Windows). Basic knowledge of programing in VBA for Excel is appreciated.

Learning outcomes and competences:

Upon successful completion of this course, students will be able to solve real problems using discrete models and methods. The emphasis is on formulation of mathematical models. Students will get acquainted with optimization methods and heuristic approaches. Graduates of the course will be able to create models in the optimization system MPL for Windows and to make elementary macros in VBA for Excel.

Course contents:

  1. Integer programing problem. Mixed-integer programing problem.
  2. Formulation of models of integer and mixed-integer programing problems.
  3. Cutting stock problem. Knapsack problem. Assignment problems.
  4. Set-covering problem. Set-partitioning problem. Plant location problem. Fixed-cost problem.
  5. Bin Packing Problem. Container transportation problem.
  6. Graph modeling. Maximal flow problem. Minimal spanning tree problem. Minimal Steiner tree problem.
  7. Routing problems. Chinese postman problem. Travelling salesman problem. Vehicle routing problem.
  8. Polyhedral theory. Theory of valid inequalities. Strengthening inequalities.
  9. Methods for solving mixed-integer programing problems. Relaxations of discrete problems.
  10. Cutting-plane methods. Branch and bound method.
  11. Computational complexity.
  12. Heuristics and metaheuristics.