Combinatorial Optimization Problems

In many fields of industry and technology solving complex optimization problems is the key to increasing productivity and product quality. It is the objective of a combinatorial optimization method to search for the best solution out of a very large number of possible solutions. Normally, the best solution means the solution with the lowest costs or the solution with the highest profit.

Simply checking or enumerating all possible solutions of real-world problems would take thousands of years even if using the fastest supercomputers of the world. Classical approaches (e.g. linear integer programming) on the other hand, are not at all efficient in this case. Now, the use of parallel computing shows a way out of this deadlock.

In our research group efficient parallel methods and algorithms were developed to solve optimization problems. These methods can extend the conventional productions planning systems, e.g. in airline industry, transportation, and logistics.

Together with a large German airline and partners at other universities we are now developing parallel methods for fleet assignment and crew scheduling. Another industrial project investigates parallel approaches for vehicle routing and route planning in transportation industry.

Methods for optimization are

• Parallel Branch & Bound
• Parallel Simulated Annealing
• Parallel Tabu Search

If you are interested, please contact Torsten Fahle or Meinolf Sellmann.