Extending Linear Relaxation for User Interface Layout

Linear relaxation is a common method for solving linear problems as they occur in science and engineering. In contrast to direct methods such as Gauss-elimination or QR-factorization, linear relaxation is inherently efficient for problems with sparse matrices as they are often encountered, for instance, in the application domain of constraint-based UI layout. However, the linear relaxation method 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 the UI layout problem. In this paper we extend linear relaxation to non-square matrices and soft constraints, and identify pivot assignment as the major issue to overcome in this process. We propose two algorithms for pivot assignment: random pivot assignment, and a more complex deterministic pivot assignment algorithm. Compared to the standard pivot assignment, which selects the elements on the diagonal of the problem matrix as pivot elements, these algorithms make the solving process more robust and make it possible to solve non-square matrices. Furthermore, we propose two algorithms for solving specifications containing soft constraints: constraint insertion and constraint removal. With these algorithms, it is possible to prioritize constraints. That is, if there are conflicting constraints in a specification as is commonly the case for UI layout, only the constraints with lower priority are violated to resolve the conflict. The performance and convergence of the proposed algorithms are evaluated empirically using randomly generated UI layout specifications of various sizes. The results show that our best linear relaxation algorithm performs significantly better than that of LP-Solve, which is a well-known efficient linear programming solver, and QR-decomposition.