Problème d'ensembles indépendantes

Ce problème d'optimisation combinatoire se rencontre chaque fois qu'il s'agit de minimiser une fonction de coût en présence de contraintes rigides. On peut formaliser le problème sous la forme suivante:

Soit un ensemble de configurations et un ensemble de configruations réalisables (satisfaisant les contraintes). Soit une fonction de coût. Trouver les tels que pour tout .

Pour ce faire, on introduit une fonction , pour définie par

pour tout . Le paramètre est un facteur de pénalité. Les solutions réalisables contribuent uniquement au premier terme de la somme -- en l'abaissant -- tandis que les configurations irréalisables contribuent au premier et au second termes. Pour trouver donc l'ensemble indépendant maximal on peut utiliser l'algorithme du recuit simulé pour minimiser la fonction .

La procédure suivante donne un mouvement isotherme de l'algorithme de minimisation.