Constraint Solving for User Interface Layout Problems

Abstract

This thesis proposes efficient and robust algorithms for solving linear constraints problems for graphical user interface (GUI) layout. Constraints have been recognised as a powerful method for the specification of GUI layouts for a long time. Most constraint problems encountered in this area are sparse, i.e. most linear coefficients in the corresponding coefficient matrix are zero. The numerical methods that have been proposed for solving layout problems so far are mainly direct methods. The focus of this research is on investigating iterative methods for solving these problems efficiently. The algorithms developed in this thesis are compared to well-known direct and linear programming algorithms. The performance and convergence of the proposed and existing algorithms were evaluated empirically using randomly generated UI layout specifications of various sizes. Successive Over-Relaxation (SOR) is one of the most commonly used iterative methods for solving linear problems, and this was the first algorithm investigated in this thesis. In contrast to direct methods such as Gauss-elimination or QR-factorization, SOR is particularly efficient for problems with sparse matrices, as they appear in GUI layout specifications. However, SOR as described in the literature has its limitations: it works only with square matrices and does not support soft constraints, which makes it inapplicable to UI layout problems. This research extends SOR so that it can be used to solve non-square matrices and soft constraints. Furthermore, different optimizations of SOR were investigated to speed up its convergence. First, we propose a metric to measure the optimality of a constraint sequence and then a Simulated Annealing based algorithm, that optimizes the order in which constraints are solved. Second, we propose Constraint-Wise Under-relaxation (CWU), a technique in which the relaxation parameters of individual constraints are adjusted during solving. Third, we investigate the use of a warm start strategy, which reuses the solution of a previous layout to warm start the solving of a new layout, taking into account that most layout changes during runtime are small. Another contribution of this thesis is an investigation of the Kaczmarz method – an iterative orthogonal projection algorithm – for solving GUI layout problems. This algorithm is more efficient than the SOR algorithm and its convergence is guaranteed. However, to make it applicable to GUI problems some extensions were necessary, such as support for soft constraints. We also investigate some approaches for least-squares solving and optimization in this context.