F. J. Rodriguez, F. Glover, C. García-Martínez, R. Martí, M. Lozano, GRASP with exterior path-relinking and restricted local search for the multidimensional two-way number partitioning problem.

1. Abstract
2. Experimental Comparison
   1. Detailed Results
   2. GRASP+ePR: executable version

Abstract

In this work, we tackle multidimensional two-way number partitioning (MDTWNP) problem by combining GRASP with Exterior Path Relinking. In the last few years, the combination of GRASP with path relinking (PR) has emerged as a highly effective tool for finding high-quality solutions for several difficult problems in reasonable computational time. However, in most of the cases, this hybridization is limited to the variant known as interior PR. Here, we couple GRASP with the ”exterior form” of path relinking and perform extensive experimentation to evaluate this variant. In addition, we enhance our GRASP with PR method with a novel local search method specially designed for the MDTWNP problem. Our computational experiments show the superiority of this approach compared with the previous best method for MDTWNP and with alternative methods for this problem that use other forms of PR.

Experimental Comparison

Detailed Results

The detailed results of each algorithm for both the tuning and state-of-the-art comparison sections are available here. 

GRASP+ePR: executable version

We provide an executable version of our algorithm for Linux x64 systems. For more information on how to use it, please refer to the Readme.txt file that it is provided with the executable.