Le problème de Maximum Satisfiability (MAX-SAT) est un problème classique en optimisation. Etant données n variables booléennes x1, x2, .., xn, et m clauses (relations logiques "OU" entre les variables), on cherche les valeurs des variables telles que le plus possible de clauses valent VRAI.
Ce problème est considéré comme difficile, c'est-à-dire qu'on ne connaît pas d'algorithme permettant de calculer l'optimal efficacement pour n'importe quel jeu de données. Vous commencerez par proposer un algorithme permettant d'obtenir une solution faisable, puis travaillerez sur un algorithme d'affectation aléatoire en cherchant des garanties sur sa performance. Ces deux algorithmes seront implémentés et testés sur des instances que vous générerez vous-mêmes avec Java.