|Title:||Two metaheuristic approaches for solving multidimensional two-way number partitioning problem||Journal:||Computers and Operations Research||Volume:||46||First page:||59||Last page:||68||Issue Date:||1-Jun-2014||Rank:||M21||ISSN:||0305-0548||DOI:||10.1016/j.cor.2014.01.003||Abstract:||
In this paper, we address two metaheuristic approaches, a Variable Neighborhood Search (VNS) and an Electromagnetism-like metaheuristic (EM), on an NP-hard optimization problem: Multi-dimensional Two-way Number Partitioning Problem (MDTWNPP). MDTWNPP is a generalization of a Two-way Number Partitioning Problem (TWNPP), where a set of vectors is partitioned rather than a set of numbers. The simple k-swap neighborhoods allow an effective shaking procedure in the VNS search. The attraction-repulsion mechanism of EM is extended with a scaling procedure, which additionally moves EM points closer to local optima. Both VNS and EM use the same local search procedure based on 1-swap improvements. Computational results were obtained on 210 standard instances. Direct comparison with results from the literature confirm the significance of applying these methods to MDTWNPP.
|Keywords:||Combinatorial optimization | Metaheuristics | Number partitioning||Publisher:||Elsevier||Project:||Mathematical Modelas and Optimization Methods on Large-Scale Systems
Graph theory and mathematical programming with applications in chemistry and computer science
Show full item record
checked on Feb 2, 2023
checked on Feb 3, 2023
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.