Combinatorial optimization

Combinatorial optimization

THE'combinatorial optimization, also called discrete optimization, est une branche de l’optimisation en math appliquées et en informatique, également liée à la recherche opérationnelle, l’algorithmique et la théorie de la complexity. L’optimisation combinatoire consiste à trouver dans un ensemble un sous-ensemble contenant les « meilleures solutions ».

Finding an optimal solution in a discrete and finite set is an easy problem in theory: you just have to try all the solutions, and compare their qualities to see the best. However, the combinatorial explosion of possible solutions of certain mathematical problems does not make it possible to obtain a solution in a "human" time.

Quelques problèmes d’optimisation combinatoire peuvent être résolus (de manière exacte) en temps polynomial par exemple par un algorithme de dynamic programming ou en montrant que le problème peut être formulé comme un problème d’optimisation linéaire en variables réelles. Dans la plupart des cas, le problème est Np-difficile et, pour le résoudre, il faut faire appel à des algorithmes adaptés.

In practice, the physically acceptable complexity is often only polynomial. We are then satisfied with having a solution approximated at best, obtained by a heuristic or a meta-heuristic. It is important to note that some of these methods provide global optimals, the difference with the exact methods is the fact of not having a formal proof (mathematical or finality proof) of its global optimality.

combinatorial optimization technique

Solution tree

That is E l’ensemble des solutions des problèmes. Il est supposé discret et fini. L’énumération des solutions se représente en tree. Tous les éléments de E are separated into not sous-ensemble non vides disjoints contenant chacun une partie de l’ensemble des solutions. Par exemple, l’ensemble peut être séparé en deux dans le problème du backpack si on prend ou non un élément xk in the bag.

The operation can be repeated for each subset until each set contains only one element. For the backpack example, each sub-assembly is separated until a decision is reached on the last element.

The root of the tree is E, the wires are the sub-assemblies etc. as shown in the following diagram:

enumeration optimization

Solving techniques

Exact

These methods give a guarantee to find the optimal solution for an instance of finite size in a limited time and to prove its optimality.

Heuristic

When the complexity of a problem is exponential or presents a combinatorial explosion, the use of heuristics is recommended. This is a method that quickly provides a "good" solution to the problem. This approximate solution can then provide a starting point for using an exact method (such as the Northwest corner for the transport problem). All greedy and naive algorithms are heuristics.

It should be noted that heuristics are built to solve a given problem, and cannot be used in other conditions unlike meta-heuristics. Heuristics are evaluated according to three criteria:

  1. Qualité du résultat : l’heuristique est confrontée aux results optimaux pour un ensemble de valeurs du problème donné (on parle de benchmark). La qualité de la solution peut soit être une distance à la solution optimale, soit une probabilité de l’atteindre.
  2. Cost of heuristics: complexity in time and space.
  3. Field of application: the field of admissibility of all the variables.

The heuristics for a given problem are numerous, so it is important to provide a fast one and provide "good" results.

Meta-heuristic

Meta-heuristics have a higher level of abstraction than heuristics since it is a method that can adapt to a given problem. Thus, the methods can be applied to various problems (in the form of a black box) without modifying their operation. We also speak of generalist heuristics.

There are two kinds of meta-heuristics: population (To) or course (b). Most algorithms do not have a determined population, so it is possible to use the algorithm for a route or a population.

population path metaheuristic

Both kinds work with the same four-step process:

  1. Neighborhood : the neighborhood of a solution is a subset of solutions that can be reached by a transformation of the initial solution (by permutation, by extension, by mutation, by ejection, etc.).
  2. Exploration : exploration consists of collecting data on the entire neighborhood.
  3. Operation : the operation uses the information collected to define the “interesting” areas of the research area formed by the neighborhood.
  4. Memory : the memory takes learning into account and makes it possible to determine the zones likely to have a global optimum. If the new solutions or the stopping criteria no longer allow the solution to be improved, the algorithm stops. Otherwise, return to step 1. Certain algorithms only work with stopping criteria, so we are talking about memoryless meta-heuristics.

optimization algorithm

To share
en_GBEN
%d bloggers like this: