Research report 2003 - Max Planck Institute for Informatics
Combinatorical optimization
Authors
Friedrich Eisenbrand; Markus Behle
Departments
Kombinatorische Optimierung (Dr. habil. Martin Skutella)
MPI für Informatik, Saarbrücken
Summary
Combinatorial Optimization deals with the identification of optimal choices in a large set of alternatives. This topic is of great importance in many fields of applications, such as planning, crew
scheduling portfolio management and many more.
In this report we give an introduction to combinatorial optimization with the help of a famous example, the traveling salesman problem. Then we describe the integer programming approach to combinatorial optimization and describe two of our results in this area. One concerns the generation of cutting planes and one concerns the complexity of integer programming in fixed dimension.