Visual search tree profiling

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

    Research output: Contribution to journalArticleResearchpeer-review

    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

    Shishmarev, Maxim ; Mears, Christopher ; Tack, Guido ; Garcia De La Banda, Maria . / Visual search tree profiling. In: Constraints. 2016 ; Vol. 21, No. 1. pp. 77-94.
    @article{47a10fc1d03f44199f7edd4f4b30810c,
    title = "Visual search tree profiling",
    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.",
    keywords = "Constraint programming, Search tree, Profiling, Comparison, Visualisation",
    author = "Maxim Shishmarev and Christopher Mears and Guido Tack and {Garcia De La Banda}, Maria",
    year = "2016",
    doi = "10.1007/s10601-015-9202-1",
    language = "English",
    volume = "21",
    pages = "77--94",
    journal = "Constraints",
    issn = "1383-7133",
    publisher = "Springer-Verlag London Ltd.",
    number = "1",

    }

    Visual search tree profiling. / Shishmarev, Maxim ; Mears, Christopher ; Tack, Guido; Garcia De La Banda, Maria .

    In: Constraints, Vol. 21, No. 1, 2016, p. 77-94.

    Research output: Contribution to journalArticleResearchpeer-review

    TY - JOUR

    T1 - Visual search tree profiling

    AU - Shishmarev, Maxim

    AU - Mears, Christopher

    AU - Tack, Guido

    AU - Garcia De La Banda, Maria

    PY - 2016

    Y1 - 2016

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

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

    KW - Constraint programming

    KW - Search tree

    KW - Profiling

    KW - Comparison

    KW - Visualisation

    U2 - 10.1007/s10601-015-9202-1

    DO - 10.1007/s10601-015-9202-1

    M3 - Article

    VL - 21

    SP - 77

    EP - 94

    JO - Constraints

    JF - Constraints

    SN - 1383-7133

    IS - 1

    ER -