Decomposition methods for solving PCSP (Partial Constraint Satisfaction Problem) : application to FAP and graph coloring problems
Méthodes de décomposition pour la résolution des PCSP (Partial Constraint Satisfaction Problem) : application aux problèmes FAP et coloration de graphes
Résumé
The wide range of potential applications concerned by the resolution of Partial Constraints Satisfaction Problems (PCSP) justifies the growing interest of scientists in this class of problems. Solving a PCSP means searching for values to assign to the decision variables in order to maximize (or minimize) a predefined objective function. These problems are NP-hard, so there isn’t an exact approach nor an efficient heuristic able to provide the optimal solution for large instances. In order to solve effectively the difficult instances, numerous approaches based on hybridization, learning or decomposition are proposed. In the present work, we focus on the latter proposal, which consists in splitting the PCSP into several smaller size PCSPs and we propose some methods to solve the decomposed problem. Two wide axes are explored : the resolution based on the decomposition and the one guided by decomposition. The former solves separately the difficult parts of the decomposed problem (cuts or clusters) and then combines partial solutions obtained in order to achieve a global solution for the original problem. The latter aims at benefiting from the structure of the problem to be decomposed in order to accelerate its resolution while ensuring optimal or near optimal solutions. All the proposed algorithms are tested and validated on the well-known benchmarks of PCSP problems such as Frequency Assignment Problem (FAP) and graph coloring problem
Les applications réelles liées aux problèmes de satisfaction partielle de contraintes (PCSP : Partial Constraints Satisfaction Problem) sont de plus en plus nombreuses, ce qui justifie l’intérêt croissant des chercheurs pour cette classe de problèmes. La résolution d’un PCSP revient à affecter des valeurs à toutes ses variables tout en maximisant (ou minimisant) une fonction objectif prédéfinie. Ces problèmes sont NP-difficiles, par conséquent il n’existe aucune approche aussi bien exacte qu’heuristique efficace sur les grandes instances. Pour résoudre efficacement les instances difficiles, une multitude de solutions sont proposées, allant de l’hybridation à l’apprentissage en passant par la décomposition. Dans notre travail, nous nous intéressons à cette dernière proposition, qui consiste à fractionner le problème PCSP en plusieurs sous-problèmes PCSP de tailles raisonnables, puis proposer des algorithmes de résolution pour les problèmes décomposés. Cette approche a pour but de bénéficier de la structure du problème afin d’accélérer sa résolution tout en garantissant des solutions optimales ou sous-optimales. Deux grand axes sont explorés : les approches basées sur la décomposition et celles guidées par la décomposition. Les approches basées sur la décomposition consistent à résoudre séparément les parties difficiles du problème décomposé, puis combiner les solutions partielles obtenues en vue d’atteindre une solution globale du problème d’origine. Les approches guidées par la décomposition consistent à développer des métaheuristiques qui tiennent compte de la structure du problème décomposé. Les algorithmes proposés sont testés et validés sur des instances réelles des problèmes PSCP, comme le problème d’affectation de fréquences et le problème de coloration de graphes