Open AccessCHN and Swap Heuristic to Solve the Maximum Independent Set Problem
Author(s) -
Adil Bouhouch,
Chakir Loqman,
El Qadi Abderrahime
Publication year - 2017
Publication title -
international journal of electrical and computer engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.277
H-Index - 22
ISSN - 2088-8708
DOI - 10.11591/ijece.v7i6.pp3583-3592
Subject(s) - computer science , mathematical optimization , swap (finance) , set (abstract data type) , heuristic , constraint (computer aided design) , graph , local search (optimization) , independent set , artificial neural network , algorithm , mathematics , theoretical computer science , artificial intelligence , geometry , finance , economics , programming language
We describe a new approach to solve the problem to find the maximum independent set in a given Graph, known also as Max-Stable set problem (MSSP). In this paper, we show how Max-Stable problem can be reformulated into a linear problem under quadratic constraints, and then we resolve the QP result by a hybrid approach based Continuous Hopfeild Neural Network (CHN) and Local Search. In a manner that the solution given by the CHN will be the starting point of the local search. The new approach showed a good performance than the original one which executes a suite of CHN runs, at each execution a new leaner constraint is added into the resolved model. To prove the efficiency of our approach, we present some computational experiments of solving random generated problem and typical MSSP instances of real life problem.