Please use this identifier to cite or link to this item: https://research.matf.bg.ac.rs/handle/123456789/1315
Title: Self-adaptive CMSA for solving the multidimensional multi-way number partitioning problem
Authors: Djukanović, Marko
Kartelj, Aleksandar 
Blum, Christian
Affiliations: Informatics and Computer Science 
Keywords: Hybrid metaheuristics;Local search;MILP models;Number partitioning problem
Issue Date: 1-Dec-2023
Rank: M21a
Publisher: Elsevier
Journal: Expert Systems with Applications
Abstract: 
The multidimensional multi-way number partitioning problem takes as input a set of n vectors with a fixed dimension m≥2, and aims to find a partitioning of this set into k≥2 non-empty subsets, such that the sums per coordinate across all subsets are as similar as possible. The problem has applications in key encryption, multiprocessor scheduling, minimization of circuit size and delay, and clustering. This paper employs a hybrid meta-heuristic, a self-adaptive version of the Construct, Merge, Solve, and Adapt algorithm equipped with an efficient local search procedure. Local search was able to accelerate the convergence towards promising regions of the search space. A comprehensive experimental evaluation shows that the proposed algorithm improves over all four competing algorithms from the related literature, especially when it comes to instances with higher k-values, i.e. k≥3. The observed average relative differences are for several instance groups larger than 25% in favor of the proposed algorithm compared to the second-best approach. In fact, a statistical evaluation indicates that our algorithm performs significantly better than the other approaches on all instances with k≥3.
Description: 
Copyright by Elsevier
DOI: https://doi.org/10.1016/j.eswa.2023.120762
URI: https://research.matf.bg.ac.rs/handle/123456789/1315
ISSN: 09574174
DOI: 10.1016/j.eswa.2023.120762
Rights: Attribution-NonCommercial-NoDerivs 3.0 United States
Appears in Collections:Research outputs

Files in This Item:
File Description SizeFormat Existing users please
djukanovic_kartelj_clean_version__ESWA.pdf611.36 kBAdobe PDF
Embargoed until January 1, 2026    Request a copy
Show full item record

SCOPUSTM   
Citations

3
checked on Dec 21, 2024

Page view(s)

25
checked on Dec 24, 2024

Google ScholarTM

Check

Altmetric

Altmetric


This item is licensed under a Creative Commons License Creative Commons