Compiling constraint solving using projection

Warwick Harvey, Peter J. Stuckey, Alan Borning

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

11 Citations (Scopus)

Abstract

Linear equality and inequality constraints arise naturally in specifying many aspects of user interfaces, such as requiring that one window be to the left of another, requiring that a pane occupy the left-most 1/3 of a window, or preferring that an object be contained within a rectangle if possible. For interactive use, we need to solve similar constraint satisfaction problems repeatedly for each screen refresh, with each successive problem differing from the previous one only in the position of an input device and the previous state of the system. We present an algorithm for solving such systems of constraints using projection. The solution is compiled into very efficient, constraint-free code, which is parameterized by the new inputs. Producing straight-line, constraint-free code of this sort is important in a number of applications: for example, to provide predictable performance in real-time systems, to allow companies to ship products without including a runtime constraint solver, to compile Java applets that can be downloaded and run remotely (again without having to include a runtime solver), or for applications where runtime efficiency is particularly important. Even for less time-critical user interface applications, the smooth performance of the resulting code is more pleasing than that of code produced using other current techniques.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming - CP 1997 - 3rd International Conference, CP 1997, Proceedings
EditorsGert Smolka
PublisherSpringer
Pages491-505
Number of pages15
ISBN (Print)3540637532, 9783540637530
Publication statusPublished - 1 Jan 1997
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 1997 - Linz, Austria
Duration: 29 Oct 19971 Nov 1997
Conference number: 3rd

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1330
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 1997
Abbreviated titleCP 1997
CountryAustria
CityLinz
Period29/10/971/11/97

Cite this

Harvey, W., Stuckey, P. J., & Borning, A. (1997). Compiling constraint solving using projection. In G. Smolka (Ed.), Principles and Practice of Constraint Programming - CP 1997 - 3rd International Conference, CP 1997, Proceedings (pp. 491-505). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1330). Springer.