Russian doll search algorithms for discrete optimization problems

Julkaisun otsikon käännös: Russian doll search algorithms for discrete optimization problems

Vesa Vaskelainen

    Tutkimustuotos: Doctoral ThesisCollection of Articles


    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.
    Julkaisun otsikon käännösRussian doll search algorithms for discrete optimization problems
    Myöntävä instituutio
    • Aalto-yliopisto
    • Östergård, Patric, Vastuuprofessori
    • Östergård, Patric, Ohjaaja
    Painoksen ISBN978-952-60-3409-6
    Sähköinen ISBN978-952-60-3410-2
    TilaJulkaistu - 2010
    OKM-julkaisutyyppiG5 Artikkeliväitöskirja


    Sukella tutkimusaiheisiin 'Russian doll search algorithms for discrete optimization problems'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

    Siteeraa tätä