Relaxation continue
En informatique théorique et 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. Le ratio entre la solution optimale de la relaxation et du problème initial est appelé integrality gap. Portail de l'analyse Portail de l'informatique théorique
Pour les articles homonymes, voir Relaxation.
Cet article est une ébauche concernant l’informatique.
En informatique théorique et 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. Le ratio entre la solution optimale de la relaxation et du problème initial est appelé integrality gap.
