Solving Linear Arithmetic Constraints for User Interface Applications

Authors: Alan Borning, Kim Marriott, Peter Stuckey, and Yi Xiao

Proceedings of the 1997 ACM Symposium on User Interface Software and Technology, October 1997, pages 87-96.

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. Current constraint solvers designed for UI applications cannot efficiently handle simultaneous linear equations and inequalities. This is a major limitation. We describe incremental algorithms based on the dual simplex and active set methods that can solve such systems of constraints efficiently.

full paper (pdf)

A companion technical report, "Solving Linear Arithmetic Constraints for User Interface Applications: Algorithm Details", UW tech report 97-06-01, contains additional information on the algorithms.

Constraints home page