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 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article