Méthodes de décomposition pour la résolution des PCSP (Partial Constraint Satisfaction Problem) : application aux problèmes FAP et coloration de graphes

Abstract : 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
Document type :
Theses
File URL :
http://docnum.univ-lorraine.fr/ulprive/DDOC_T_2016_0314_SADEG.pdf
Complete list of metadatas

https://hal.univ-lorraine.fr/tel-01752409
Contributor : Thèses Ul <>
Submitted on : Thursday, March 29, 2018 - 1:45:17 PM
Last modification on : Friday, March 30, 2018 - 1:28:55 AM

Identifiers

  • HAL Id : tel-01752409, version 1

Collections

Citation

Lamia Sadeg. Méthodes de décomposition pour la résolution des PCSP (Partial Constraint Satisfaction Problem) : application aux problèmes FAP et coloration de graphes. Autre [cs.OH]. Université de Lorraine, 2016. Français. ⟨NNT : 2016LORR0314⟩. ⟨tel-01752409⟩

Share

Metrics

Record views

13