Abstract
Russian doll search is applied to finding maximum independent sets in hypergraphs, focusing on a particular subproblem of the hitting set problem, the Steiner triple covering problem. An instance denoted A 135 is solved considerably faster with Russian doll search than with integer linear programming and a state-of-the-art optimization tool (using otherwise a similar established approach to split the problem into subproblems). In addition, the improvement in speed makes it possible to carry out a search proving that all optimal solutions for A 135 are isomorphic.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Avis D.: A note on some computationally difficult set covering problems. Math. Programm. 18, 138–145 (1980)
Colbourn C.J., Rosa A.: Triple Systems. Oxford University Press, Oxford (1999)
Fulkerson D.R., Nemhauser G.L., Trotter L.E.: Two computationally difficult set covering problems that arise in computing the 1-width of incidence matrices of Steiner triple systems. Math. Programm. Stud. 2, 72–81 (1974)
Hall M. Jr: Combinatorial Theory. Blaisdell, Waltham (1967)
Heras F., Larrosa J., Oliveras A.: MiniMaxSat an efficient weighted Max-SAT solver. J. Artif. Intell. Res. 31, 1–32 (2008)
Heras F., Larrosa J.: A Max-SAT inference-based pre-processing for Max-Clique. In: Büning, H.K., Zhao, X. (eds) Theory and Applications of Satisfiability Testing, Proceedings of the 11th International Conference (SAT 2008), LNCS, vol. 4996, pp. 139–152. Springer, Berlin (2008)
Kaski P., Östergård P.R.J.: Classification Algorithms for Codes and Designs. Springer, Berlin (2006)
Mannino C., Sassano A.: Solving hard set covering problems. Oper. Res. Lett. 18, 1–5 (1995)
Meseguer P., Sánchez M.: Specializing Russian doll search. In: Walsh, T. (eds) Principles and Practice of Constraint Programming, Proceedings of the 7th International Conference (CP 2001), LNCS, vol. 2239, pp. 464–478. Springer, Berlin (2001)
Odijk M.A., van Maaren H.: Improved solutions to the Steiner triple covering problem. Inform. Process. Lett. 65, 67–69 (1998)
Östergård P.R.J.: A fast algorithm for the maximum clique problem. Discrete Appl. Math. 120, 197–207 (2002)
Ostrowski, J.: Symmetry in Integer Programming. PhD thesis, Lehigh University (2009)
Ostrowski J., Linderoth J., Rossi F., Smriglio S.: Constraint orbital branching. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds) Integer Programming and Combinatorial Optimization, Proceedings of the 13th International Conference (IPCO 2008), LNCS, vol. 5035, pp. 225–239. Springer, Berlin (2008)
Sanchez, M., Allouche, D., de Givry, S., Schiex, T.: Russian doll search with tree decomposition, In: Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI’09), pp. 603–608. Morgan Kaufmann, San Francisco (2009)
Verfaillie, G., Lemaître, M., Schiex, T.: Russian doll search for solving constraint optimization problems. In: Proceedings of the 13th National Conference on Artificial Intelligence (AAAI-96), pp. 181–187. AAAI Press, Menlo Park (1996)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Östergård, P.R.J., Vaskelainen, V.P. Russian doll search for the Steiner triple covering problem. Optim Lett 5, 631–638 (2011). https://doi.org/10.1007/s11590-010-0225-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-010-0225-7