Tabu search with feasible and infeasible searches for equitable coloring. (May 2018)

• Record Type: Journal Article
• Authors: Wang, Wenyu; Hao, Jin-Kao; Wu, Qinghua
• Is Part Of: Engineering applications of artificial intelligence. Volume 71(2017:Nov.)
• Page Start: 1
• Page End: 14
• Publication Date: 2018-05
• Subjects: Tabu search -- Heuristics -- Infeasible local search -- Equitable coloring -- Vertex coloring; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2018.01.012
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: The equitable coloring problem is a variant of the classical graph coloring problem that arises from a number of real-life applications where the cardinality of color classes must be balanced. In this paper, we present a highly effective hybrid tabu search method for the problem. Based on three complementary neighborhoods, the algorithm alternates between a feasible local search phase where the search focuses on the most relevant feasible solutions and an infeasible local search phase where a controlled exploration of infeasible solutions is allowed by relaxing the equity constraint. A novel cyclic exchange neighborhood is also proposed in order to enhance the search ability of the hybrid tabu search algorithm. Experiments on a set of 73 benchmark instances in the literature indicate that the proposed algorithm is able to find improved best solutions for 15 instances (new upper bounds) and matches the best-known solutions for 57 instances. Additional analyses show the interest of the cyclic exchange neighborhood and the hybrid scheme combining both feasible and infeasible local searches.