Skip to main content
Top
Published in: Journal of Combinatorial Optimization 2/2016

01-08-2016

A three-phased local search approach for the clique partitioning problem

Authors: Yi Zhou, Jin-Kao Hao, Adrien Goëffon

Published in: Journal of Combinatorial Optimization | Issue 2/2016

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper presents a three-phased local search heuristic CPP-P\(^{3}\) for solving the Clique Partitioning Problem (CPP). CPP-P\(^{3}\) iterates a descent search, an exploration search and a directed perturbation. We also define the Top Move of a vertex, in order to build a restricted and focused neighborhood. The exploration search is ensured by a tabu procedure, while the directed perturbation uses a GRASP-like method. To assess the performance of the proposed approach, we carry out extensive experiments on benchmark instances of the literature as well as newly generated instances. We demonstrate the effectiveness of our approach with respect to the current best performing algorithms both in terms of solution quality and computation efficiency. We present improved best solutions for a number of benchmark instances. Additional analyses are shown to highlight the critical role of the Top Move-based neighborhood for the performance of our algorithm and the relation between instance hardness and algorithm behavior.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Footnotes
1
If some groups contain exactly one vertex, then several moves lead to equivalent solutions. Thus, |N(s)| can be slightly inferior to \(k \times |V|\).
 
2
The source code will be available upon publication of the paper at: http://​www.​info.​univ-angers.​fr/​pub/​hao/​cpp.​html.
 
Literature
go back to reference Benlic U, Hao JK (2011) A multilevel memetic approach for improving graph k-partitions. IEEE Trans Evol Comput 15(5):624–642CrossRef Benlic U, Hao JK (2011) A multilevel memetic approach for improving graph k-partitions. IEEE Trans Evol Comput 15(5):624–642CrossRef
go back to reference Benlic U, Hao JK (2013) Breakout local search for the quadratic assignment problem. Appl Math Comput 219(9):4800–4815MathSciNetMATH Benlic U, Hao JK (2013) Breakout local search for the quadratic assignment problem. Appl Math Comput 219(9):4800–4815MathSciNetMATH
go back to reference Brimberg J, Janićijević S, Mladenović N, Urošević D (2015) Solving the clique partitioning problem as a maximally diverse grouping problem. Optim Lett doi:10.1007/s11590-015-0869-4 Brimberg J, Janićijević S, Mladenović N, Urošević D (2015) Solving the clique partitioning problem as a maximally diverse grouping problem. Optim Lett doi:10.​1007/​s11590-015-0869-4
go back to reference Brusco MJ, Köhn HF (2009) Clustering qualitative data based on binary equivalence relations: neighborhood search heuristics for the clique partitioning problem. Psychometrika 74(4):685–703MathSciNetCrossRefMATH Brusco MJ, Köhn HF (2009) Clustering qualitative data based on binary equivalence relations: neighborhood search heuristics for the clique partitioning problem. Psychometrika 74(4):685–703MathSciNetCrossRefMATH
go back to reference Chen Y, Hao JK (2015) Iterated responsive threshold search for the quadratic multiple knapsack problem. Ann Oper Res 226(1):101–131MathSciNetCrossRefMATH Chen Y, Hao JK (2015) Iterated responsive threshold search for the quadratic multiple knapsack problem. Ann Oper Res 226(1):101–131MathSciNetCrossRefMATH
go back to reference De Amorim SG, Barthélemy JP, Ribeiro CC (1992) Clustering and clique partitioning: simulated annealing and tabu search approaches. J Classif 9(1):17–41MathSciNetCrossRef De Amorim SG, Barthélemy JP, Ribeiro CC (1992) Clustering and clique partitioning: simulated annealing and tabu search approaches. J Classif 9(1):17–41MathSciNetCrossRef
go back to reference Dorndorf U, Jaehn F, Pesch E (2008) Modelling robust flight-gate scheduling as a clique partitioning problem. Transp Sci 42(3):292–301CrossRef Dorndorf U, Jaehn F, Pesch E (2008) Modelling robust flight-gate scheduling as a clique partitioning problem. Transp Sci 42(3):292–301CrossRef
go back to reference Fu ZH, Hao JK (2015) A three-phase search approach for the quadratic minimum spanning tree problem. Eng Appl Artif Intell 46:113–130CrossRef Fu ZH, Hao JK (2015) A three-phase search approach for the quadratic minimum spanning tree problem. Eng Appl Artif Intell 46:113–130CrossRef
go back to reference Galinier P, Boujbel Z, Fernandes MC (2011) An efficient memetic algorithm for the graph partitioning problem. Ann Oper Res 191(1):1–22MathSciNetCrossRefMATH Galinier P, Boujbel Z, Fernandes MC (2011) An efficient memetic algorithm for the graph partitioning problem. Ann Oper Res 191(1):1–22MathSciNetCrossRefMATH
go back to reference Hao JK (2012) Memetic algorithms in discrete optimization. In: Neri F, Cotta C, Moscato P (Eds) Handbook of memetic algorithms. Studies in Computational Intelligence, vol 379, Chapter 6, pp 73–94 Hao JK (2012) Memetic algorithms in discrete optimization. In: Neri F, Cotta C, Moscato P (Eds) Handbook of memetic algorithms. Studies in Computational Intelligence, vol 379, Chapter 6, pp 73–94
go back to reference Jaehn F, Pesch E (2013) New bounds and constraint propagation techniques for the clique partitioning problem. Discret Appl Math 161(13–14):2025–2037MathSciNetCrossRefMATH Jaehn F, Pesch E (2013) New bounds and constraint propagation techniques for the clique partitioning problem. Discret Appl Math 161(13–14):2025–2037MathSciNetCrossRefMATH
go back to reference Jin Y, Hao JK, Hamiez JP (2014) A memetic algorithm for the minimum sum coloring problem. Comput Oper Res 43(3):318–327MathSciNetCrossRef Jin Y, Hao JK, Hamiez JP (2014) A memetic algorithm for the minimum sum coloring problem. Comput Oper Res 43(3):318–327MathSciNetCrossRef
go back to reference Ji X, Mitchell JE (2007) Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement. Discret Optim 4(1):87–102MathSciNetCrossRefMATH Ji X, Mitchell JE (2007) Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement. Discret Optim 4(1):87–102MathSciNetCrossRefMATH
go back to reference Jones T, Forrest S (1995) Fitness distance correlation as a measure of problem difficulty for genetic algorithms. In: Proceedings of the 6th international conference on genetic algorithms. Morgan Kaufmann Publishers Inc, San Francisco, pp 184–192 Jones T, Forrest S (1995) Fitness distance correlation as a measure of problem difficulty for genetic algorithms. In: Proceedings of the 6th international conference on genetic algorithms. Morgan Kaufmann Publishers Inc, San Francisco, pp 184–192
go back to reference Kernighan BW, Lin S (1970) An efficient heuristic procedure for partitioning graphs. Bell Syst Tech J 49(2):291–307CrossRefMATH Kernighan BW, Lin S (1970) An efficient heuristic procedure for partitioning graphs. Bell Syst Tech J 49(2):291–307CrossRefMATH
go back to reference Lourenço HR, Martin OC, Stützle T (2003) Iterated local search. Handbook of metaheuristics, vol 57. Kluwer Academic Publishers, New York, pp 320–353 Lourenço HR, Martin OC, Stützle T (2003) Iterated local search. Handbook of metaheuristics, vol 57. Kluwer Academic Publishers, New York, pp 320–353
go back to reference Moscato P, Cotta C (2003) A Gentle Introduction to memetic algorithms. In: Glover F, Kochenberger GA (eds) Handbook of metaheuristic. Kluwer, Norwell Moscato P, Cotta C (2003) A Gentle Introduction to memetic algorithms. In: Glover F, Kochenberger GA (eds) Handbook of metaheuristic. Kluwer, Norwell
go back to reference Palubeckis G, Ostreika A, Tomkevičius A (2014) An iterated tabu search approach for the clique partitioning problem. Sci World J 2014:353101CrossRef Palubeckis G, Ostreika A, Tomkevičius A (2014) An iterated tabu search approach for the clique partitioning problem. Sci World J 2014:353101CrossRef
go back to reference Rand WM (1971) Objective criteria for the evaluation of clustering methods. J Am Stat Assoc 66(336):846–850CrossRef Rand WM (1971) Objective criteria for the evaluation of clustering methods. J Am Stat Assoc 66(336):846–850CrossRef
go back to reference Wakabayashi Y (1986) Aggregation of binary relations: algorithmic and polyhedral investigations. PhD thesis, Universität Ausburg, Augsburg Wakabayashi Y (1986) Aggregation of binary relations: algorithmic and polyhedral investigations. PhD thesis, Universität Ausburg, Augsburg
go back to reference Wang H, Alidaee B, Glover F, Kochenberger G (2006) Solving group technology problems via clique partitioning. Int J Flex Manuf Syst 18(2):77–97CrossRefMATH Wang H, Alidaee B, Glover F, Kochenberger G (2006) Solving group technology problems via clique partitioning. Int J Flex Manuf Syst 18(2):77–97CrossRefMATH
Metadata
Title
A three-phased local search approach for the clique partitioning problem
Authors
Yi Zhou
Jin-Kao Hao
Adrien Goëffon
Publication date
01-08-2016
Publisher
Springer US
Published in
Journal of Combinatorial Optimization / Issue 2/2016
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-015-9964-9

Other articles of this Issue 2/2016

Journal of Combinatorial Optimization 2/2016 Go to the issue

Premium Partner