Constraints reordering to speed up successive over-relaxation for constraint-based user interface layouts

摘要

If successive over-relaxation (SOR) is applied to linear systems, the ordering in which constraints are solved affects the convergence behaviour of the algorithm. A bad ordering can slow down the convergence whereas a good ordering can speed it up. To overcome this problem, we propose an algorithm that reorders the sequence of constraints used during solving in an optimal way. Our contribution consists of, first, a metric to measure the optimality of a constraint sequence and, second, a simulated annealing based algorithm, which optimizes the order of constraints. The performance of sequence optimization is evaluated empirically using randomly generated UI layout specifications of various sizes. The results show that our proposed algorithm speeds up the convergence of SOR for constraint-based UIs.