The Cassowary linear arithmetic constraint solving algorithm. 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 third of a window, or preferring that an object be contained within a rectangle if possible. Previous constraint solvers designed for user interface applications cannot handle simultaneous linear equations and inequalities efficiently. This is a major limitation, as such systems of constraints arise often in natural declarative specifications. We describe Cassowary---an incremental algorithm based on the dual simplex method, which can solve such systems of constraints efficiently. We have implemented the algorithm as part of a constraint-solving toolkit. We discuss the implementation of the toolkit, its application programming interface, and its performance.

References in zbMATH (referenced in 11 articles )

Showing results 1 to 11 of 11.
Sorted by year (citations)

  1. Yue Jiang, Wolfgang Stuerzlinger, Matthias Zwicker, Christof Lutteroth: ORCSolver: An Efficient Solver for Adaptive GUI Layout with OR-Constraints (2020) arXiv
  2. Jamil, Noreen; Mirza, Farhaan; Naeem, M. Asif; Baghaei, Nilufar: A refinement of an iterative orthogonal projection method (2018)
  3. Jamil, Noreen; Müller, Johannes; Naeem, M. Asif; Lutteroth, Christof; Weber, Gerald: Extending linear relaxation for non-square matrices and soft constraints (2016)
  4. Jamil, Noreen; Chen, Xuemei; Cloninger, Alexander: Hildreth’s algorithm with applications to soft constraints for user interface layout (2015)
  5. German, V. N.: Solving linear constraints over real and rational fields (2010)
  6. Tran, Duc-Khanh; Ringeissen, Christophe; Ranise, Silvio; Kirchner, Hélène: Combination of convex theories: modularity, deduction completeness, and explanation (2010)
  7. Hölzl, Matthias; Meier, Max; Wirsing, Martin: Which soft constraints do you prefer? (2009)
  8. Lutteroth, Christof; Strandh, Robert; Weber, Gerald: Domain specific high-level constraints for user interface layout (2008)
  9. Bozzano, Marco; Bruttomesso, Roberto; Cimatti, Alessandro; Junttila, Tommi; van Rossum, Peter; Schulz, Stephan; Sebastiani, Roberto: M\textbfathSAT: Tight integration of SAT and mathematical decision procedures (2005)
  10. Shin, Ji-Ae; Davis, Ernest: Processes and continuous change in a SAT-based planner (2005)
  11. Badros, Greg J.; Borning, Alan; Stuckey, Peter J.: The cassowary linear arithmetic constraint solving algorithm. (2001) ioport