Authors: Kratica, Jozef 
Kojić, Jelena
Savić, Aleksandar
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
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 Jun 16, 2024

Page view(s)

checked on May 10, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.