×

zbMATH — the first resource for mathematics

Model-driven visualizations of constraint-based local search. (English) Zbl 1179.68141
Summary: Visualization is often invaluable to understand the behavior of optimization algorithms, identify their bottlenecks or pathological behaviors, and suggest remedial techniques. Yet developing visualizations is often a tedious activity requiring significant time and expertise. This paper presents a framework for the visualization of Constraint-Based Local Search (CBLS) algorithms. Given a high-level model and a declarative visualization specification, the CBLS visualizer systematically produces animations to visualize constraints and objectives, violations, and conflicts, as well as the temporal behavior of these measures. The visualization specification is declarative and typically composed of a triple (what,where,how) indicating what to display, where, and with which graphical objects. The visualizer architecture is compositional and extensible. It provides building blocks which can be assembled freely by the user and focuses almost exclusively on static aspects, the dynamic aspects being automated by the use of invariants. The paper highlights various functionalities of the visualizer and describes a blueprint for its implementation.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Borning, A. (1981). The programming language aspects of ThingLab, a constraint-oriented simulation laboratory. ACM Transaction on Programming Languages and Systems, 3(4), 353–387. · doi:10.1145/357146.357147
[2] Carro, M., & Hermenegildo, M. (2000). Tools for constraint visualisation: The VIFID/TRIFID tool. In P. Deransart, M. V. Hermenegildo, & J. Maluszynski (Eds.), Analysis and visualization tools for constraint programming. New York: Springer.
[3] Carro, M., & Hermenegildo, M. (2000). Tools for search-tree visualisation: The APT tool. In P. Deransart, M. V. Hermenegildo, & J. Maluszynski (Eds.), Analysis and visualization tools for constraint programming. New York: Springer.
[4] Deransart, P., Hermenegildo, M., & Maluszynski, J. (Eds.) (2000). Analysis and visualization tools for constraint programming, constraint debugging (DiSCiPl project). London: Springer.
[5] Dincbas, M., Van Hentenryck, P., Simonis, H., Aggoun, A., Graf, T., & Berthier, F. (1988). The constraint logic programming language CHIP. In Proceedings of the international conference on fifth-generation computer systems.
[6] Goualard, F., & Benhamou, F. (2000). Debugging constraint programs by store inspection. In P. Deransart, M. V. Hermenegildo, & J. Maluszynski (Eds.), Analysis and visualization tools for constraint programming. New York: Springer.
[7] Helm, R., & Marriott, K. (1986). Declarative graphics. In ICLP’86 (pp. 513–527).
[8] Hosobe, H. (2000). A scalable linear constraint solver for user interface construction. In CP’2000 (pp. 218–232). · Zbl 1044.68768
[9] Meier, M. (1995). Debugging constraint programs. In CP’1995 (pp. 204–221).
[10] Schulte, C. (1997). Oz Explorer: A visual constraint programming tool. In ICLP’97 (pp. 286–300). Leuven, Belgium, July.
[11] Simonis, H., & Aggoun, A. (2000). Search-tree visualisation. In P. Deransart, M. V. Hermenegildo, & J. Maluszynski (Eds.), Analysis and visualization tools for constraint programming. New York: Springer.
[12] Simonis, H., Aggoun, A., Beldiceanu, N., & Bourreau, E. (2000). Complex constraint abstraction: Global constraint visualisation. In P. Deransart, M. V. Hermenegildo, & J. Maluszynski (Eds.), Analysis and visualization tools for constraint programming. New York: Springer.
[13] Sutherland, I. E. (1963). Sketchpad, a man-machine graphical communication system. In Outstanding dissertations in the computer sciences. New York: Garland.
[14] Van Hentenryck, P. (2007). Constraint programming as declarative algorithmics. In F. Benhamou, N. Jussien, & B. O’Sullivan (Eds.), Trends in constraint programming. Lyon: Hermes.
[15] Van Hentenryck, P., & Michel, L. (2005). Constraint-based local search. Cambridge: MIT. · Zbl 1153.90582
[16] Van Hentenryck, P., & Michel, L. (2007). Synthesis of constraint-based local search algorithms from high-level models. In AAAI’07. July.
[17] Van Hentenryck, P., Michel, L., Paulin, P., & Puget, J. F. (2004). The OPL studio modeling system. In J. Kallrath (Ed.), Modeling languages in mathematical optimization (pp. 43–76). Dordrecht: Kluwer.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.