Relaxation continue

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Relaxation.
Domaine admissible discret (en rouge) et sa relaxation continue (en bleue)

En recherche opérationnelle, la relaxation continue est une méthode qui consiste à interpréter de façon continue un problème combinatoire ou discret. Cette méthode est utilisée afin d'obtenir des informations sur le problème discret initial et parfois même pour obtenir sa solution.

Les problèmes discrets ou combinatoires sont en effet très difficiles à traiter en raison de l'explosion combinatoire et il est courant de les traiter par une méthode de séparation et évaluation (branch and bound en anglais) : la relaxation continue fait partie des algorithmes d'évaluation nécessaire à la mise en œuvre de cette méthode.

Lors d'une optimisation linéaire en nombres entiers la relaxation continue s'avère à la fois efficace et facile à mettre en œuvre.

Dans un problème de minimisation la relaxation continue fournit une borne inférieure de la solution du problème initial discret. En effet, la minimisation continue se fait sur un ensemble contenant l'ensemble des points admissibles du problème discret.