Russian doll search algorithms for discrete optimization problems

Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Aalto-yliopiston teknillinen korkeakoulu | Doctoral thesis (article-based)
Checking the digitized thesis and permission for publishing
Instructions for the author
Degree programme
Verkkokirja (1101 KB, 36 s.)
Report / Helsinki University of Technology, Department of Communications and Networking, 7/2010
This dissertation discusses exhaustive search algorithms for discrete optimization problems. The search space of the problems is pruned by determining different lower or upper bounds for the solution of the problem. In some cases, redundant candidates can be pruned on the basis of structural symmetry. One effective approach to prune the search space is Russian doll search, which is based on the idea of dividing a problem into smaller subproblems that are subsequently solved in an ascending order. The solutions to the previous subproblems are then used to further prune, in order to solve the next subproblem. The final subproblem is, then, the original problem. In this work, Russian doll search is applied to some optimization problems in digraphs and hypergraphs. The problems considered are the 'Steiner triple covering problem', the 'maximum transitive subtournament problem', and the 'best barbeque problem'. The Steiner triple covering problem is a hitting set problem that corresponds to a search for a vertex cover from a hypergraph. A search for a transitive subtournament from a digraph can be translated to a search for an independent set from a hypergraph. Moreover, the best barbeque problem can be presented as a problem on hypergraphs. The performance of the implemented algorithms was experimentally evaluated. For example, the Russian doll search algorithm for the Steiner triple covering problem A135 has solved an instance approximately 100 times faster than the leading commercial software for integer programming. In the best barbeque problem context, the relevant parameters of test instances comprised the complete range of relevant parameters for real biological instances. Algorithms designed to find the maximum (order of) transitive subtournaments have succeeded in all but eight directed graphs, of up to five vertices, determining the lower bounds for Sperner capacities that meet the upper bounds, obtained by other methods. In addition, a new record, a tournament of order 14, in which tournament winners are disjoint by using the definitions developed by Banks and Slater, is discovered with the algorithms for finding the maximum (order of) transitive subtournaments.
Supervising professor
Östergård, Patric, Prof.
Thesis advisor
Östergård, Patric, Prof.
backtrack search, digraphs, Russian doll search, transitive tournaments
Other note
  • [Publication 1]: Patric R. J. Östergård, Vesa Vaskelainen, and Axel Mosig. 2007. Algorithms for the combinatorial best barbeque problem. MATCH Communications in Mathematical and in Computer Chemistry, volume 58, number 2, pages 309-321. © 2007 by authors.
  • [Publication 2]: Lasse Kiviluoto, Patric R. J. Östergård, and Vesa P. Vaskelainen. 2010. Algorithms for finding maximum transitive subtournaments. Espoo, Finland: Aalto University School of Science and Technology. 15 pages. Helsinki University of Technology, Department of Communications and Networking, Report 5/2010. ISBN 978-952-60-3369-3. ISSN 1797-478X. © 2010 by authors.
  • [Publication 3]: Vesa P. Vaskelainen and Vesa Riihimäki. 2009. Bounds for the sample size in performance testing of combinatorial algorithms. InterStat, July 2009, paper no. 6, 14 pages. © 2009 by authors.
  • [Publication 4]: Patric R. J. Östergård and Vesa P. Vaskelainen. Russian doll search for the Steiner triple covering problem. Optimization Letters, to appear, 8 pages.
  • [Publication 5]: Lasse Kiviluoto, Patric R. J. Östergård, and Vesa P. Vaskelainen. 2009. Sperner capacity of small digraphs. Advances in Mathematics of Communications, volume 3, number 2, pages 125-133. © 2009 American Institute of Mathematical Sciences (AIMS). By permission.
  • [Publication 6]: Patric R. J. Östergård and Vesa P. Vaskelainen. 2010. A tournament of order 14 with disjoint Banks and Slater sets. Discrete Applied Mathematics, volume 158, number 5, pages 588-591.