L'article aborde un problème classique d'optimisation combinatoire connu sous le nom de problème de couverture d'ensemble, illustré par une situation concrète où des étudiants doivent préparer des examens dans M matières différentes. Ils disposent de N livres, chacun couvrant un sous-ensemble spécifique de ces matières. L'objectif est de déterminer la sélection minimale de livres qui permet de couvrir l'ensemble des matières au programme, ce qui correspond mathématiquement à trouver le plus petit ensemble de livres dont l'union des matières couvertes inclut toutes les M disciplines.
La méthode proposée consiste à reformuler ce problème de couverture en un problème de satisfiabilité booléenne (SAT), permettant ainsi d'utiliser des solveurs SAT efficaces pour trouver la solution optimale. Cette transformation implique de modéliser les contraintes de couverture complète et d'optimisation du nombre de livres sélectionnés sous forme de clauses logiques. L'approche offre l'avantage de bénéficier des avancées récentes dans les algorithmes de résolution SAT, particulièrement performants pour ce type de problèmes combinatoires.
L'article détaille probablement les étapes de cette modélisation, expliquant comment encoder les relations entre livres et matières en variables booléennes, et comment formuler les contraintes de couverture et de minimalité. Cette méthodologie s'applique à divers domaines au-delà du contexte éducatif, notamment en planification, en logistique ou en conception de réseaux, où se posent des problèmes similaires de sélection optimale sous contraintes de couverture.