Abstract
The completion problem arises in various domains, including flexible manufacturing systems, logistics, telecommunications, and marketing. Its objective is to group or cluster a given set of available orders or customers within distribution warehouses or marketing management. This problem is widely recognized as a challenging discrete optimization problem classified as NP-Hard. This paper introduces an augmented population method that combines two key features: discrete particle swarm optimization and an \(\varepsilon \)-enlarging threshold operator. The method adopts an oscillating strategy, alternating between the \(\varepsilon \)-enlarging threshold operator and the periodic enhancement operator of particle positions at each step. This strategy aims to exploit information acquired through the enlarging strategy to extend the search to unvisited search spaces. Throughout the search process, both strategies work to maintain the diversity of the reference set, preventing premature convergence and stagnation on local optima. To evaluate the proposed method’s behavior and performance, benchmark instances from the existing literature are used. The proposed method’s results are then compared to those achieved by the best methods available in the literature. This comparative analysis enables the establishment of new performance bounds for the problem, highlighting the effectiveness of the proposed method.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Data availability
No data availability statement.
References
Aboelfotoh A, Singh M, Suer G (2019) Order batching optimization for warehouses with cluster-picking. Proc Manuf 39:1464–1473. https://doi.org/10.1016/j.promfg.2020.01.302. In: 25th International Conference on production research manufacturing innovation: cyber physical manufacturing August 9-14, 2019, Chicago, Illinois (USA)
Ajeil FH, Ibraheem IK, Sahib MA, Humaidi AJ (2020) Multi-objective path planning of an autonomous mobile robot using hybrid pso-mfb optimization algorithm. Appl Soft Comput 89:106076
Al-Iedani N, Hifi M, Saadi T (2016) Neighborhood search-based heuristic for the k-clustering minimum biclique completion problem. In: Proceedings of the International Conference on control, decision and information technologies (CoDIT), pp 639–643. https://doi.org/10.1109/CoDIT.2016.7593637. IEEE
Cao Y, Liu J, Xu Z (2021) A hybrid particle swarm optimization algorithm for rfid network planning. Soft Comput 25:5747–5761. https://doi.org/10.1007/s00500-020-05569-1
Chegini SN, Amini P, Ahmadi B, Bagheri A, Amirmostofian I (2022) Intelligent bearing fault diagnosis using swarm decomposition method and new hybrid particle swarm optimization algorithm. Soft Comput 26:1475–1497. https://doi.org/10.1007/s00500-021-06307-x
Dantas S, Groshaus M, Guedes A, Machado RC, Ries B, Sasaki D (2017) On star and biclique edge-colorings. Int Trans Oper Res 24(1–2):339–346. https://doi.org/10.1111/itor.12307
Faure N, Chrétienne P, Gourdin E, Sourd F (2007) Biclique completion problems for multicast network design. Discrete Optim 4(3):360–377. https://doi.org/10.1016/j.disopt.2007.09.005
Glover, F, Laguna, M, Marti, R (2003) In: Ghosh, A, Tsutsui, S (eds) Scatter Search. Springer, Berlin, pp 519–537. https://doi.org/10.1007/978-3-642-18965-4_20
Gualandi S (2009) \(k\)-clustering minimum biclique completion via a hybrid cp and sdp approach. In: van Hoeve W-J, Hooker JN (eds) Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. Springer, pp 87–101. https://doi.org/10.1007/978-3-642-01929-6_8
Gualandi S, Maffioli F, Magni C (2013) A branch-and-price approach to \(k\)-clustering minimum biclique completion problem. Int Trans Oper Res 20(1):101–117. https://doi.org/10.1111/j.1475-3995.2012.00860.x
Hifi M, Sadeghsa S (2023) A rounding strategy-based algorithm for the k-clustering minimum biclique completion problem. J Oper Res Soc 74(1):258–271. https://doi.org/10.1080/01605682.2022.2035272
Hifi M, Moussa I, Saadi T, Saleh S (2015) An adaptive neighborhood search for k-clustering minimum bi-clique completion problems. In: Le Thi HA, Pham Dinh T, Nguyen NT (eds) Modelling, computation and optimization in information systems and management sciences. Springer, Cham, pp 15–25. https://doi.org/10.1007/978-3-319-18161-5_2
Kakkottakath Valappil Thekkepuryil J, Suseelan DP, Keerikkattil PM (2021) An effective meta-heuristic based multi-objective hybrid optimization method for workflow scheduling in cloud computing environment. Clust Comput 24:2367–2384
Kefale HA, Getie EM, Eshetie KG (2021) Optimal design of grid-connected solar photovoltaic system using selective particle swarm optimization. Int J Photoenergy 2021:1–9
Koch S, Wäscher G (2016) A grouping genetic algorithm for the order batching problem in distribution warehouses. J Bus Econ 86(1–2):131–153. https://doi.org/10.1007/s11573-015-0789-x
Korte B, Vygen J (2018) Springer, Berlin. Heidelberg. https://doi.org/10.1007/978-3-662-56039-6
Laguna M (2018) In: Martí R, Pardalos PM, Resende MGC (eds) Tabu Search. Springer, Cham, pp 741–758. https://doi.org/10.1007/978-3-319-07124-4_24
Liu Y, Kim K (2023) An artificial-intelligence-driven product design framework with a synergistic combination of genetic algorithm and particle swarm optimization. Soft Comput 27:17621–17638. https://doi.org/10.1007/s00500-023-09223-4
Sahu C, Parhi DR (2022) Navigational strategy of a biped robot using regression-adaptive pso approach. Soft Comput 26:12317–2341. https://doi.org/10.1007/s00500-022-07084-x
Smail MA, Wu X, Henkel ND, Eby HM, Herman JP, McCullumsmith RE, Shukla R (2021) Similarities and dissimilarities between psychiatric cluster disorders. Mol Psychiatry 26(9):4853–4863
Subramaniyan M, Skoogh A, Muhammad AS, Bokrantz J, Johansson B, Roser C (2020) A generic hierarchical clustering approach for detecting bottlenecks in manufacturing. J Manuf Syst 55:143–158
van der Zee D-J (2017) Coordinating batching decisions in manufacturing networks. Int J Prod Res 55(18):5405–5422. https://doi.org/10.1080/00207543.2017.1317926
Wang D, Tan D, Liu L (2018) Particle swarm optimization algorithm: an overview. Soft Comput 22:387–408. https://doi.org/10.1007/s00500-016-2474-6
Wang Z, Zhang C, Li H, Zhao Y (2021) A multi agent-based optimal control method for combined cooling and power systems with thermal energy storage. In: Building simulation, vol. 14. Springer, pp 1709–1723
Zhang W, Wang X, Zhao D, Tang X (2012) Graph degree linkage: Agglomerative clustering on a directed graph. In: Computer Vision–ECCV 2012: 12th European Conference on computer vision, Florence, Italy, October 7-13, 2012, Proceedings, Part I 12, pp. 428–441. Springer
Funding
The authors have not disclosed any funding.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Ethical approval
This article does not contain any studies with human participants performed by any of the authors.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
All authors are listed in alphabetical order of their last name according to the Operational Research domain in France.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Cochard, GM., Elmi Samod, S., Hifi, M. et al. An augmented swarm optimization algorithm for k-clustering minimum biclique completion problems. Soft Comput (2024). https://doi.org/10.1007/s00500-024-09822-9
Accepted:
Published:
DOI: https://doi.org/10.1007/s00500-024-09822-9