4EK605 Combinatorial Optimization

Aims of the course:

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

Learning outcomes and competencies:

Upon successful completion of this course, students will be able to solve real problems using discrete models and methods. The emphasis is on the 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 programming problem. Mixed-integer programming problem.
  2. Formulation of models of integer and mixed-integer programming 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. Traveling salesman problem. Vehicle routing problem.
  8. Polyhedral theory. Theory of valid inequalities. Strengthening inequalities.
  9. Methods for solving mixed-integer programming problems. Relaxations of discrete problems.
  10. Cutting-plane methods. Branch and bound method.
  11. Computational complexity.
  12. Heuristics and metaheuristics.