Title: Combining graph decomposition techniques and metaheuristics for solving PCSPs. Application to MI-FAP
Authors: Lamia Sadeg-Belkacem; Zineb Habbas; Wassila Aggoune-Mtalaa; Fatima Benbouzid-Si Tayeb
Addresses: Ecole Militaire Polytechnique, Algeria; Ecole Nationale Supérieure d'Informatique, Algeria; Université de Lorraine, France ' Université de Lorraine, France ' Luxembourg Institute of Science and Technology, Luxembourg ' Ecole Nationale Supérieure d'Informatique, Algeria
Abstract: This paper presents a study towards a framework for solving discrete optimisation problems modelled as partial constraint satisfaction problems (PCSPs). These studies follow two approaches, namely a bottom-up, and a top-down one. Three decomposition methods and an adaptive genetic algorithm (AGA) are associated with these approaches. The experimental results obtained for MI-FAP problems show a good trade-off between the quality of the solution and the execution time of the different algorithms.
Keywords: discrete optimisation problems; partial constraint satisfaction problem; PCSP; frequency assignment problem; FAP; graph decomposition; adaptive genetic algorithms; AGA; metaheuristics.
DOI: 10.1504/IJRIS.2016.082960
International Journal of Reasoning-based Intelligent Systems, 2016 Vol.8 No.3/4, pp.104 - 118
Received: 03 Dec 2014
Accepted: 03 Jan 2016
Published online: 17 Mar 2017 *