Un problème de nombres entiers où les points rouges représentent des solutions admissibles peut être assoupli avec, par exemple, la zone rouge ou la zone bleue (où tous les points dans les zones sont des solutions admissibles).
En mathématiques, une technique de relaxation est une méthode d'optimisation qui consiste en la résolution d'un problème d'optimisation difficile par le biais de problèmes d'optimisations plus approchables numériquement, mais dont les solutions ne fournissent pas immédiatement de garantie concernant la résolution ou non du problème initial .
Généralement, les techniques de relaxation consistent à remplacer des contraintes strictes du problème en des contrainte moins strictes dans un problème similaire. On peut citer par exemple :
la relaxation continue, qui consiste à interpréter de manière continue un problème d’optimisation portant sur des variables à valeurs discrètes,
la relaxation lagrangienne, qui consiste à supprimer des contraintes en les intégrant dans la fonction objectif (en pénalisant le non respect de ces dernières).
Trouver une solution au problème d'optimisation relaxé ne garantit alors pas immédiatement qu'il existe une solution au problème initial , mais les solutions trouvées permettent au moins de s'approcher d'une solution admissible. C'est d'une certaine manière l'opposé d'une approche par ajout de conservatisme.
Les techniques de relaxation sont largement utilisées dans les méthodes de séparation et évaluation.
