Geodesic
An Integer Linear Programming Formulation and Genetic Algorithm for the Maximum Set Splitting Problem
Publications de l'Institut Mathématique, _N_S_92 (2012) no. 106, p. 25

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

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.
Classification : 90C10 90C59 65K05
Keywords: integer linear programming, genetic algorithm, set splitting, Steiner triple systems 
@article{PIM_2012_N_S_92_106_a1,
     author = {Bojana Lazovi\'c and Miroslav Mari\'c and Vladimir Filipovi\'c and Aleksandar Savi\'c},
     title = {An {Integer} {Linear} {Programming} {Formulation} and {Genetic} {Algorithm} for the {Maximum} {Set} {Splitting} {Problem}},
     journal = {Publications de l'Institut Math\'ematique},
     pages = {25 },
     publisher = {mathdoc},
     volume = {_N_S_92},
     number = {106},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PIM_2012_N_S_92_106_a1/}
}
TY  - JOUR
AU  - Bojana Lazović
AU  - Miroslav Marić
AU  - Vladimir Filipović
AU  - Aleksandar Savić
TI  - An Integer Linear Programming Formulation and Genetic Algorithm for the Maximum Set Splitting Problem
JO  - Publications de l'Institut Mathématique
PY  - 2012
SP  - 25 
VL  - _N_S_92
IS  - 106
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PIM_2012_N_S_92_106_a1/
LA  - en
ID  - PIM_2012_N_S_92_106_a1
ER  - 
%0 Journal Article
%A Bojana Lazović
%A Miroslav Marić
%A Vladimir Filipović
%A Aleksandar Savić
%T An Integer Linear Programming Formulation and Genetic Algorithm for the Maximum Set Splitting Problem
%J Publications de l'Institut Mathématique
%D 2012
%P 25 
%V _N_S_92
%N 106
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PIM_2012_N_S_92_106_a1/
%G en
%F PIM_2012_N_S_92_106_a1
Bojana Lazović; Miroslav Marić; Vladimir Filipović; Aleksandar Savić. An Integer Linear Programming Formulation and Genetic Algorithm for the Maximum Set Splitting Problem. Publications de l'Institut Mathématique, _N_S_92 (2012) no. 106, p. 25 . http://geodesic.mathdoc.fr/item/PIM_2012_N_S_92_106_a1/