The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.
Aalto

Russian Doll Search Algorithms for Discrete Optimization Problems

Vesa Vaskelainen

Doctoral dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the Faculty of Electronics, Communications and Automation for public examination and debate in Auditorium S4 at the Aalto University School of Science and Technology (Espoo, Finland) on the 19th of November 2010 at 12 noon.

Overview in PDF format (ISBN 978-952-60-3410-2)   [1101 KB]
Dissertation is also available in print (ISBN 978-952-60-3409-6)

Abstract

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.

This thesis consists of an overview and of the following 6 publications:

  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.
  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.
  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.
  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.
  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.
  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.

Keywords: backtrack search, digraphs, Russian doll search, transitive tournaments

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

© 2010 Aalto University School of Science and Technology

Last update 2011-05-26