A large number of real-world planning problems called combinatorial

optimization problems share the following properties: They are optimiza-

tion problems, are easy to state, and have a nite but usually very large

number of feasible solutions. While some of these as e.g. the Shortest Path

problem and the Minimum Spanning Tree problem have polynomial algo-

ritms, the majority of the problems in addition share the property that no

polynomial method for their solution is known.