top
This paper presents a Variable neighbourhood search (VNS)
approach for solving the Maximum Set Splitting Problem (MSSP). The algorithm forms a system of neighborhoods based on changing the component for an increasing number of elements. An efficient local search procedure swaps the components of pairs of elements and yields a relatively short running time. Numerical experiments are performed on the instances known in the literature: minimum hitting set and Steiner triple systems. Computational results show that the proposed VNS achieves all optimal or best known solutions in short times. The experiments indicate that the VNS compares favorably with other methods previously used for solving the MSSP. ACM Computing Classification System (1998): I.2.8.
Matic, Dragan. "A Variable Neighborhood Search Approach for Solving the Maximum Set Splitting Problem." Serdica Journal of Computing 6.4 (2012): 369-384. <http://eudml.org/doc/250883>.
@article{Matic2012, abstract = {This paper presents a Variable neighbourhood search (VNS)
approach for solving the Maximum Set Splitting Problem (MSSP). The algorithm forms a system of neighborhoods based on changing the component for an increasing number of elements. An efficient local search procedure swaps the components of pairs of elements and yields a relatively short running time. Numerical experiments are performed on the instances known in the literature: minimum hitting set and Steiner triple systems. Computational results show that the proposed VNS achieves all optimal or best known solutions in short times. The experiments indicate that the VNS compares favorably with other methods previously used for solving the MSSP. ACM Computing Classification System (1998): I.2.8.}, author = {Matic, Dragan}, journal = {Serdica Journal of Computing}, keywords = {Variable Neighborhood Search; Combinatorial Optimization; Maximum Set Splitting Problem; 2-Coloring of the Hypergraph; Steiner Triple Systems}, language = {eng}, number = {4}, pages = {369-384}, publisher = {Institute of Mathematics and Informatics Bulgarian Academy of Sciences}, title = {A Variable Neighborhood Search Approach for Solving the Maximum Set Splitting Problem}, url = {http://eudml.org/doc/250883}, volume = {6}, year = {2012}, }
TY - JOUR AU - Matic, Dragan TI - A Variable Neighborhood Search Approach for Solving the Maximum Set Splitting Problem JO - Serdica Journal of Computing PY - 2012 PB - Institute of Mathematics and Informatics Bulgarian Academy of Sciences VL - 6 IS - 4 SP - 369 EP - 384 AB - This paper presents a Variable neighbourhood search (VNS)
approach for solving the Maximum Set Splitting Problem (MSSP). The algorithm forms a system of neighborhoods based on changing the component for an increasing number of elements. An efficient local search procedure swaps the components of pairs of elements and yields a relatively short running time. Numerical experiments are performed on the instances known in the literature: minimum hitting set and Steiner triple systems. Computational results show that the proposed VNS achieves all optimal or best known solutions in short times. The experiments indicate that the VNS compares favorably with other methods previously used for solving the MSSP. ACM Computing Classification System (1998): I.2.8. LA - eng KW - Variable Neighborhood Search; Combinatorial Optimization; Maximum Set Splitting Problem; 2-Coloring of the Hypergraph; Steiner Triple Systems UR - http://eudml.org/doc/250883 ER -