Hildreth's algorithm with applications to soft constraints for user interface layout
From MaRDI portal
Publication:2351069
Abstract: The Hildreth's algorithm is a row action method for solving large systems of inequalities. This algorithm is efficient for problems with sparse matrices, as opposed to direct methods such as Gaussian elimination or QR-factorization. We apply the Hildreth's algorithm, as well as a randomized version, along with prioritized selection of the inequalities, to efficiently detect the highest priority feasible subsystem of equations. We prove convergence results and feasibility criteria for both cyclic and randomized Hildreth's algorithm, as well as a mixed algorithm which uses Hildreth's algorithm for inequalities and Kaczmarz algorithm for equalities. These prioritized, sparse systems of inequalities commonly appear in constraint-based user interface (UI) layout specifications. The performance and convergence of these proposed algorithms are evaluated empirically using randomly generated UI layout specifications of various sizes. The results show that these methods offer improvements in performance over standard methods like Matlab's LINPROG, a well-known efficient linear programming solver, and the recent developed Kaczmarz algorithm with prioritized IIS detection.
Recommendations
- A Mathematical Model for the Motion of a Towed Pipeline Bundle
- Extending linear relaxation for non-square matrices and soft constraints
- scientific article; zbMATH DE number 2080309
- Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
- A conjugate gradient algorithm for sparse linear inequalities
Cites work
- scientific article; zbMATH DE number 2080309 (Why is no real title available?)
- scientific article; zbMATH DE number 1853005 (Why is no real title available?)
- scientific article; zbMATH DE number 3296905 (Why is no real title available?)
- A randomized Kaczmarz algorithm with exponential convergence
- A two-phase relaxation-based heuristic for the maximum feasible subsystem problem
- Almost sure convergence of the Kaczmarz algorithm with random measurements
- Analyzing Infeasible Mixed-Integer and Integer Linear Programs
- Branch-and-Cut for the Maximum Feasible Subsystem Problem
- Convergence of the cyclical relaxation method for linear inequalities
- Detecting IIS in infeasible linear programmes using techniques from goal programming
- Domain specific high-level constraints for user interface layout
- Extensions of Hildreth’s Row-Action Method for Quadratic Programming
- Fast heuristics for the maximum feasible subsystem problem
- Locating Minimal Infeasible Constraint Sets in Linear Programs
- Misclassification minimization
- On the convergence properties of Hildreth's quadratic programming algorithm
- Preconditioning techniques for large linear systems: A survey
- Preserving Form-Features in Interactive Mesh Deformation
- Randomized Kaczmarz solver for noisy linear systems
- Randomized extended Kaczmarz for solving least squares
- Randomized methods for linear constraints: convergence rates and conditioning
- Row-Action Methods for Huge and Sparse Systems and Their Applications
- The Relaxation Method for Solving Systems of Linear Inequalities
Cited in
(7)- A Mathematical Model for the Motion of a Towed Pipeline Bundle
- Quantile-based iterative methods for corrupted systems of linear equations
- Extending linear relaxation for non-square matrices and soft constraints
- On the behaviour of the underrelaxed Hildreth's row-action method for computing projections onto Polyhedra
- The Kaczmarz algorithm, row action methods, and statistical learning algorithms
- Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions
- Metric-Constrained Optimization for Graph Clustering Algorithms
This page was built for publication: Hildreth's algorithm with applications to soft constraints for user interface layout
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2351069)
