tailieunhanh - An electromagnetism like method for the maximum set splitting problemtf

In this paper, an electromagnetism-like approach (EM) for solving the maximum set splitting problem (MSSP) is applied. Hybrid approach consisting of the movement based on the attraction-repulsion mechanisms combined with the proposed scaling technique directs EM to promising search regions. Fast implementation of the local search procedure additionally improves the efficiency of overall EM system. | Yugoslav Journal of Operations Research 23 (2013), Number 1, 31-41 DOI: AN ELECTROMAGNETISM-LIKE METHOD FOR THE MAXIMUM SET SPLITTING PROBLEM 1 TF FT Jozef KRATICA Mathematical Institute, Serbian Academy of Sciences and Arts, Kneza Mihaila 36, 11 000 Belgrade, Serbia jkratica@ Received: April 2011 / Accepted: May 2012 Abstract: In this paper, an electromagnetism-like approach (EM) for solving the maximum set splitting problem (MSSP) is applied. Hybrid approach consisting of the movement based on the attraction-repulsion mechanisms combined with the proposed scaling technique directs EM to promising search regions. Fast implementation of the local search procedure additionally improves the efficiency of overall EM system. The performance of the proposed EM approach is evaluated on two classes of instances from the literature: minimum hitting set and Steiner triple systems. The results show, except in one case, that EM reaches optimal solutions up to 500 elements and 50000 subsets on minimum hitting set instances. It also reaches all optimal/best-known solutions for Steiner triple systems. Keywords: Electromagnetism-like metaheuristic, combinatorial optimization, maximum set splitting problem, Steiner triple systems. MSC: 90C59, 90C27. 1. INTRODUCTION Let S be a finite set with cardinality m = |S| and let a family of subsets S1, ., Sn S be given. A partition of S is a disjoint pair of subsets (P1, P2) of S such that their union is equal to S, . P1 P2 = and P1 P2 = S. 1 This research was partially supported by Serbian Ministry of Education and Science under the grants no. 174010 and 174033. 32 J., Kratica / An Electromagnetism-Like Method We would like to stress that the style files and the template should not be manipulated and that the guidelines regarding font sizes and format should be adhered to. This is to ensure end product to be as homogeneous as possible. Let us define the splitting condition: a subset Sk S is