Russian doll search algorithms for discrete optimization problems

Simple item page
dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.advisorÖstergård, Patric, Prof.
dc.contributor.authorVaskelainen, Vesa 
dc.contributor.departmentTietoliikenne- ja tietoverkkotekniikan laitosfi
dc.contributor.departmentDepartment of Communications and Networkingen
dc.contributor.schoolAalto-yliopiston teknillinen korkeakoulufi
dc.contributor.supervisorÖstergård, Patric, Prof.
dc.date.accessioned2012-08-28T11:52:38Z
dc.date.available2012-08-28T11:52:38Z
dc.date.issued2010 
dc.description.abstractThis 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.en
dc.format.extentVerkkokirja (1101 KB, 36 s.) 
dc.format.mimetypeapplication/pdf 
dc.identifier.isbn978-952-60-3410-2 (electronic) 
dc.identifier.isbn978-952-60-3409-6 (printed)#8195;
dc.identifier.issn1797-4798 
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/4874
dc.identifier.urnURN:ISBN:978-952-60-3410-2 
dc.language.isoenen
dc.publisherAalto-yliopiston teknillinen korkeakouluen
dc.relation.haspart[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.en
dc.relation.haspart[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.en
dc.relation.haspart[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.en
dc.relation.haspart[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.en
dc.relation.haspart[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.en
dc.relation.haspart[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.en
dc.relation.ispartofseriesReport / Helsinki University of Technology, Department of Communications and Networking, 7/2010en
dc.subject.keywordbacktrack searchen
dc.subject.keyworddigraphsen
dc.subject.keywordRussian doll searchen
dc.subject.keywordtransitive tournamentsen
dc.subject.otherComputer science
dc.titleRussian doll search algorithms for discrete optimization problemsen
dc.typeG5 Artikkeliväitöskirjafi
dc.type.dcmitypetexten
dc.type.ontasotVäitöskirja (artikkeli)fi
dc.type.ontasotDoctoral dissertation (article-based)en
local.aalto.digiauthask
local.aalto.digifolderAalto_65108
Files
Original bundle
Now showing 1 - 5 of 5
No Thumbnail Available
Name:
isbn9789526034102.pdf
Size:
1.05 MB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
publication1.pdf
Size:
182.54 KB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
publication2.pdf
Size:
207.9 KB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
publication3.pdf
Size:
151.03 KB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
publication5.pdf
Size:
216.95 KB
Format:
Adobe Portable Document Format
Download
Collections
[diss] Sähkötekniikan korkeakoulu / ELEC