Combinatorial optimization

Combinatorial optimization is a branch of discrete mathematics. The problems looked at revolve around finding an optimal object from a set of objects, or finding an ordering of the objects in the set that is optimal according to some criteria. Examples are finding the Minimum spanning tree in a graph or the Travelling Salesman Problem. Many of the problems looked at have also been solved using linear programming.

Combinatorial Optimization Media

• 

  A minimum spanning tree of a weighted planar graph. Finding a minimum spanning tree is a common problem involving combinatorial optimization.

• 

  An optimal traveling salesperson tour through Germany’s 15 largest cities. It is the shortest among the 43,589,145,600 possible tours that visit each city exactly once.