Publications de l'Institut Mathématique, Nouvelle Série Vol. 92(106), pp. 25–34 (2012) 

AN INTEGER LINEAR PROGRAMMING FORMULATION AND GENETIC ALGORITHM FOR THE MAXIMUM SET SPLITTING PROBLEMBojana Lazovic, Miroslav Maric, Vladimir Filipovic and Aleksandar SavicFaculty of Mathematics, University of Belgrade, Belgrade, SerbiaAbstract: For the first time an integer linear programming (ILP) formulation is presented and validity of this formulation is given. We propose a genetic algorithm (GA) that uses the binary encoding and the standard genetic operators adapted to the problem. The overall performance of the GA implementation is improved by a caching technique. Experimental results are performed on two sets of instances from the literature: minimum hitting set and Steiner triple systems. The results show that CPLEX optimally solved all hitting set instances up to 500 elements and 10000 subsets. Also, it can be seen that GA routinely reached all optimal solutions up to 500 elements and 50000 subsets. The Steiner triple systems seems to be much more challenging for maximum set splitting problems since the CPLEX solved to optimality, within two hours, only two instances up to 15 elements and 35 subsets. For these instances GA reached all solutions as CPLEX but in much smaller running time. Keywords: integer linear programming, genetic algorithm, set splitting, Steiner triple systems Classification (MSC2000): 90C10; 90C59; 65K05 Full text of the article: (for faster download, first choose a mirror)
Electronic fulltext finalized on: 8 Nov 2012. This page was last modified: 19 Nov 2012.
© 2012 Mathematical Institute of the Serbian Academy of Science and Arts
