Visual search tree profiling

Maxim Shishmarev, Christopher Mears, Guido Tack, Maria Garcia De La Banda

    Research output: Contribution to journalArticleResearchpeer-review

    7 Citations (Scopus)

    Abstract

    Understanding how the search space is explored for a given constraint problem – and how it changes for different models, solvers or search strategies – is crucial for efficient solving. Yet programmers often have to rely on the crude aggregate measures of the search that are provided by solvers, or on visualisation tools that can show the search tree, but do not offer sophisticated ways to navigate and analyse it, particularly for large trees. We present an architecture for profiling a constraint programming search that is based on a lightweight instrumentation of the solver. The architecture combines a visualisation of the search tree with various tools for convenient navigation and analysis of the search. These include identifying repeated subtrees, high-level abstraction and navigation of the tree, and the comparison of two search trees. The resulting system is akin to a traditional program profiler, which helps the user to focus on the parts of the execution where an improvement to their program would have the greatest effect.
    Original languageEnglish
    Pages (from-to)77-94
    Number of pages18
    JournalConstraints
    Volume21
    Issue number1
    DOIs
    Publication statusPublished - 2016

    Keywords

    • Constraint programming
    • Search tree
    • Profiling
    • Comparison
    • Visualisation

    Cite this