The Kaczmarz method is an iterative method for solving large systems of equations that projects iterates orthogonally onto the solution space of each equation. In contrast to direct methods such as Gaussian elimination or QR-factorization, this algorithm is efficient for problems with sparse matrices, as they appear in constraint-based user interface (UI) layout specifications. However, the Kaczmarz method as described in the literature has its limitations: it considers only equality constraints and does not support soft constraints, which makes it inapplicable to the UI layout problem. In this paper we extend the Kaczmarz method for solving specifications containing soft constraints, using the prioritized IIS detection algorithm. Furthermore, the performance and convergence of the proposed algorithms are evaluated empirically using randomly generated UI layout specifications of various sizes. The results show that these methods offer improvements in performance over standard methods like Matlab's LINPROG, a well-known efficient linear programming solver.
All constraint solvers for UI layout must support over-determined systems. The commonly used techniques for dealing with over-determined problems are weighted constraints and constraint hierarchies @cite_42 @cite_11 . Weighted constraints are typically used with some general forms of direct methods, while constraint hierarchies are especially utilized in linear programming based algorithms. Many UI layout solvers are based on linear programming and support soft constraints using slack variables in the objective function @cite_28 @cite_13 @cite_5 @cite_6 .
@cite_28 @cite_42 @cite_6 @cite_5 @cite_13 @cite_11
2073536284 1504034731 2611138713 2016321606 1740773753
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. We summarize existing approaches to model and solve overconstrained problems. These problems are usually formulated as combinatorial optimization problems, and different specific and generic formalisms are discussed, including the special case of multi-objective optimization. Regarding solving methods, both systematic and local search approaches are considered. Finally we review a number of case studies on overconstrained problems taken from the specialized literature. We describe an object-oriented constraint solving toolkit, QOCA, designed for interactive graphical applications. It has a simple yet powerful interface based on the metric space model for constraint manipulation. Currently QOCA supports linear arithmetic constraints and two different metrics: the square of the Euclidean distance and the Manhattan distance. It provides three solvers, all of which rely on keeping the constraints in solved form and relies on novel algorithms for efficient resolving of constraints during direct manipulation. We provide a thorough empirical evaluation of QOCA, both of the interface design and the speed of constraint solving. Linear equality and inequality constraints arise naturally in specifying many aspects of user interfaces, such as requiring that onewindowbe 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 amajor limitation. We describe incremental algorithms based on the dual simplex and active set methods that can solve such systems of constraints efficiently. Constraint hierarchies provide a framework for soft constraints, and have been applied to areas such as artificial intelligence, logic programming, and user interfaces. In this framework, constraints are associated with hierarchical preferences or priorities called strengths, and may be relaxed if they conflict with stronger constraints. To utilize constraint hierarchies, researchers have designed and implemented various practical constraint satisfaction algorithms. Although existing algorithms can be categorized into several approaches, what kinds of algorithms are possible has been unclear from a more general viewpoint. In this paper, we propose a novel theory called generalized local propagation as a foundation of algorithms for solving constraint hierarchies. This theory formalizes a way to express algorithms as constraint scheduling, and presents theorems that support possible approaches. A benefit of this theory is that it covers algorithms using constraint hierarchy solution criteria known as global comparators, for which only a small number of algorithms have been implemented. With this theory, we provide a new classification of solution criteria based on their difficulties in constraint satisfaction. We also discuss how existing algorithms are related to our theory, which will be helpful in designing new algorithms.