Visual search tree profiling

详细信息    查看全文

• 作者：Maxim Shishmarev ; Christopher Mears ; Guido Tack ; Maria Garcia de la Banda
• 关键词：Constraint programming ; Search tree ; Profiling ; Comparison ; Visualisation
• 刊名：Constraints
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：21
• 期：1
• 页码：77-94
• 全文大小：1,710 KB
• 参考文献：1.Bauer, A., Botea, V., Brown, M., Gray, M., Harabor, D., & Slaney, J. (2010). An integrated modelling, debugging, and visualisation environment for G12. In CP 2010. LNCS, (Vol. 6308 pp. 522–536): Springer.
  2.Burch, M., Raschke, M., & Weiskopf, D. (2010). Indented pixel tree plots. In Advances in Visual Computing (pp. 338–349): Springer.
  3.Carro, M., & Hermenegildo, M. Tools for constraint visualisation: The VIFID/TRIFID tool. In: Deransart et al. [6], pp. 253–272.
  4.Choi, C.W., Lee, J.H.M., & Stuckey, P.J. (2007). Removing propagation redundant constraints in redundant modeling. ACM Transactions on Computational Logic, 8(4). doi:10.​1145/​1276920.​1276925 .
  5.Chu, G.G. (2011). Improving combinatorial optimization. Ph.D. thesis: University of Melbourne.
  6.Deransart, P., Hermenegildo, M.V., & Maluszynski, J. (Eds.) (2000). Analysis and visualization tools for constraint programming, constraint debugging (DiSCiPl project), LNCS, Vol. 1870: Springer.
  7.Deransart, P. (2004). Main results of the OADymPPaC project. In B. Demoen, & V. Lifschitz (Eds.), ICLP, LNCS, (Vol. 3132 pp. 456–457): Springer.
  8.Dooms, G., Van Hentenryck, P., & Michel, L. (2007). Model-driven visualizations of constraint-based local search. In CP 2007, LNCS, (Vol. 4741 pp. 271–285): Springer.
  9.Feydy, T., & Stuckey, P.J. (2009). Lazy clause generation reengineered. In I.P. Gent (Ed.), CP, Lecture Notes in Computer Science, (Vol. 5732 pp. 352–366): Springer.
  10.Google (2015). Protocol buffers. https://​developers.​google.​com/​protocol-buffers/​ .
  11.Goualard, F., & Benhamou, F. Debugging constraint programs by store inspection. In: Deransart et al. [6], pp. 273–297.
  12.iMatix (2015). ZeroMQ. http://​zeromq.​org .
  13.Jussien, N., Rochart, G., & Lorca, X. (2008). Choco: an open source Java constraint programming library. In CPAIOR’08 Workshop on Open-Source Software for Integer and Contraint Programming (OSSICP’08) (pp. 1–10).
  14.Meier, M. (1995). Debugging constraint programs. In CP’95, LNCS, (Vol. 976 pp. 204–221): Springer.
  15.MinisatID team (2015). MinisatID solver. https://​dtai.​cs.​kuleuven.​be/​software/​minisatid .
  16.Müller, T. (1999). Practical investigation of constraints with graph views. In K. Sagonas, & P. Tarau (Eds.) Proceedings of the International Workshop on Implementation of Declarative Languages (IDL’99).
  17.Newsham, Z., Lindsay, W., Liang, J.H., Czarnecki, K., Fischmeister, S., & Ganesh, V. (2014). SATGraf: Visualizing community structure in boolean SAT instances. https://​ece.​uwaterloo.​ca/​vganesh/​EvoGraph/​Home.​html .
  18.Schulte, C. (1997). Oz explorer: a visual constraint programming tool. In L. Naish (Ed.), ICLP (pp. 286–300): MIT Press.
  19.Schulte, C., Lagerkvist, M.Z., & Tack, G. (2006). Gecode: Generic constraint development environment. http://​www.​gecode.​org .
  20.Schulte, C., Tack, G., & Lagerkvist, M.Z. (2015). Modeling and programming with Gecode. http://​www.​gecode.​org/​doc-latest/​MPG.​pdf .
  21.Simonis, H., & Aggoun, A. Search-tree visualisation. In: Deransart et al. [6], pp. 191–208.
  22.Simonis, H., Davern, P., Feldman, J., Mehta, D., Quesada, L., & Carlsson, M. (2010). A generic visualization platform for CP. In CP 2010, LNCS, (Vol. 6308 pp. 460–474): Springer.
  23.Sinz, C. (2004). Visualizing the internal structure of SAT instances (preliminary report). In SAT.
  24.Sinz, C., & Dieringer, E.M. (2005). DPvis – a tool to visualize the structure of SAT instances. In F. Bacchus, & T. Walsh (Eds.), Theory and applications of satisfiability testing, lecture notes in computer science, (Vol. 3569 pp. 257–268). Berlin Heidelberg: Springer. doi:10.​1007/​11499107_​19 .
  25.Smith, B.M., Stergiou, K., & Walsh, T. (1999). Modelling the Golomb ruler problem. Tech. rep., University of Leeds School of Computer Studies.
  26.Van Cauwelaert, S., Lombardi, M., & Schaus, P. (2015). Understanding the potential of propagators. In Integration of AI and OR Techniques in Constraint Programming (pp. 427–436): Springer.
  27.Wallace, M.G., Novello, S., & Schimpf, J. (1997). ECLiPSe : a platform for constraint logic programming. ICL Systems Journal, 12(1).
  
• 作者单位：Maxim Shishmarev (1)
  Christopher Mears (1)
  Guido Tack (1) (2)
  Maria Garcia de la Banda (1) (2)
  
  1. Faculty of IT, Monash University, Melbourne, Australia
  2. National ICT Australia (NICTA) Victoria, Melbourne, Australia
  
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Optimization
  Computing Methodologies
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1572-9354

文摘

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