Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Adaptive feasible and infeasible tabu search for weighted vertex coloring

Abstract :

The Weighted Vertex Coloring Problem of a vertex weighted graph is to partition the vertex set into k disjoint independent sets such that the sum of the costs of these sets is minimized, where the cost of each set is given by the maximum weight of a vertex (representative) in that set. To solve this NP-hard problem, we present the adaptive feasible and infeasible search algorithm (AFISA) that relies on a mixed search strategy exploring both feasible and infeasible solutions. From an initial feasible solution, AFISA seeks improved solutions by oscillating between feasible and infeasible regions. To prevent the search from going too far from feasibility boundaries, we introduce a control mechanism that adaptively makes the algorithm to go back and forth between feasible and infeasible solutions. To explore the search space, we use a tabu search optimization procedure to ensure an intensified exploitation of candidate solutions and an adaptive perturbation strategy to escape local optimum traps. We show extensive experimental results on 161 benchmark instances and present new upper bounds that are useful for future studies. We assess the benefit of the key features of the proposed approach. This work demonstrates that examining both feasible and infeasible solutions during the search is a highly effective search strategy for the considered coloring problem and could beneficially be applied to other constrained problems as well.

Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-02715050
Contributeur : Okina Université d'Angers <>
Soumis le : lundi 1 juin 2020 - 19:56:21
Dernière modification le : mardi 2 juin 2020 - 04:03:49

Identifiants

Collections

Citation

Wen Sun, Jin-Kao Hao, Xiangjing Lai, Qinghua Wu. Adaptive feasible and infeasible tabu search for weighted vertex coloring. Information Sciences, Elsevier, 2018, 466, pp.203-219. ⟨10.1016/j.ins.2018.07.037⟩. ⟨hal-02715050⟩

Partager

Métriques

Consultations de la notice

34