Home / research areas / CO
Combinatorial Optimization
Combinatorial optimization is the science of finding the best solution out of a large but finite set of possible solutions. This large number of possibilities comes from the need to find a good subset of elements out of a given set subject to some rules. The cost or quality of a solution is usually defined as a function of these elements.
While in most practical applications scanning through all cases is only a theoretical possibility due to their immense number, combinatorial optimization tries to offer more sophisticated methods and algorithms resulting in reasonable running times. Some of the most powerful tools to find optimal solutions are linear and integer programming and constraint programming.
For those cases where these techniques can not find good solutions in reasonable time, some others approaches are possible, like Approximation algorithms, heuristics and dual bounds methods.
References:
- Christos H. Papadimitriou and Kenneth St1eiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc., Upper Saddle River, NJ, USA. 1982. Amazon