Extending linear relaxation for non-square matrices and soft constraints

摘要

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 particularly efficient for problems with sparse matrices, as they appear in constraint-based user interface (UI) layout specifications. 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.To overcome these limitations we propose two algorithms for selecting the pivot elements used during linear relaxation: random pivot assignment, and a more complex deterministic pivot assignment. Furthermore, we propose three algorithms for solving specifications containing soft constraints: prioritized IIS detection, prioritized deletion filtering and prioritized grouping constraints. With these algorithms, it is possible to prioritize constraints: if there are conflicting constraints in a specification, as it is commonly the case for UI layout, only the constraints with lower priority are violated to resolve the conflicts.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 Matlab’s LINPROG, a well-known efficient linear programming solver.