Compiling Constraint Solving using Projection
Authors: Warwick Harvey, Peter Stuckey, and Alan Borning
Proceedings of the Third International
Conference on the Principles and Practice of Constraint Programming,
pages 491-505.
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 leftmost 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.
full paper (compressed postscript)
A companion
technical
report, Computer Science Department, Melbourne University, number 97/6,
contains additional material.
Constraints home page