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.