Combinatorial Optimization Problems

Combinatorial optimization is a branch of optimization. Its domain is optimization problems where the set of feasible solutions is discrete or can be reduced to a discrete one, and the goal is to find the best possible solution.

To deal with problems of combinatorial optimization, the objective is to find the best solution or optimal solution, one that minimizes a given cost function.

There are some techniques to solve not complex problems, such as Branch and Bound or Branch and Cut. As the search space complexity grows up, the cost of those algorithms can increase exponentially, making the search of a solution not feasible.

Another way to tackle these problems is to find a suboptimal solution but in a reasonable time. In some cases you may even find the optimal solution to the problem.

Such techniques can be divided into two main groups:

  • Heuristics

  • Metaheuristics

A new emerging technology can be used to solve combinatorial optimization problems called Case Based Reasoging (CBR), in addition to these groups.

Heuristics

Can find good solutions to complex combinatorial problems by exploiting the knowledge of the application domain. Heuristic algorithms are easy to implement and find good solutions with relatively small computational effort, however, resign (from the theoretical point of view) to find the global optimum solution of a
problem. In large problems rarely a heuristic algorithm finds the best solution.

Metaheuristics

Metaheuristic algorithms are general purpose algorithms, which do not depend on the problem and offer good results but usually not "the best solution". Are usually
used for problems without an specific algorithm or heuristic solver, or when it is not useful to implement these methods.


Algorithms Classification

Figure based in the next image from wikipedia.