Combinatorial Optimization


To put it simply: Combinatorial Optimization entails making an optimal decision when there are a lot of alternatives to choose from. Let’s take a look at one of the most popular problems in Combinatorial Optimization:

The Travelling Salesman Problem

A travelling salesman needs to visit 50 clients and wants to know in which order he should visit them so that the total length of the routes that he has to take is as short as possible. Either he knows the distance between any 2 of his clients or he can work it out by consulting a map beforehand.

The alternative choices that the salesman has in this problem are the different orders in which he can visit his clients. There are a total of 50!=50*49*48*…*2*1 different variations, corresponding to a number with 65 digits after the decimal point. In this context, the optimal decision would be the one that most minimizes the total length of the routes to be traversed.

Comparing all the different possibilities and selecting the shortest route is simply not feasible, because even counting from 1 to 50! would take a supercomputer from here to eternity. Combinatorial Optimization applies mathematical methods to radically limit the number of possible alternatives from the onset, so that optimal or near optimal routes may be found more quickly. Other classical problems that Combinatorial Optimization deals with are, for example

  • Tour planning: what is the quickest route from a departure point to a destination? Along which routes should goods be transported?
  • Allocation problems: In which order and on which processors should orders be processed?
  • Compiling flight schedules: How can flight crews be allocated to flights so that the numerous constraints, such as rest periods, are not violated?
  • Location planning: Where should hospitals be built? Where should warehouses be rented?

But we do not always look for an optimal solution. Sometimes, it is more important to develop a fast procedure which finds a solution that is almost opttimal instead of spending more time to look for the optimum.