Hildreth's algorithm with applications to soft constraints for user interface layout

DOI10.1016/J.CAM.2015.04.014MaRDI QIDQ2351069zbMATH OpenOpenAlexFDO

Authors Noreen Jamil, Xuemei Chen, Alexander Cloninger

Publication date 22 June 2015

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.2902

zbMATH Keywords

Hildreth's algorithmlinear inequalitiessoft constraintsUI layout

Mathematics Subject Classification ID

Numerical linear algebra (65F99) Numerical mathematical programming methods (65K05) Linear programming (90C05)

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

• 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
• 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?)
• 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 extended Kaczmarz for solving least squares
• Randomized Kaczmarz solver for noisy linear systems
• 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

(10)

• A refinement of an iterative orthogonal projection method
• A Mathematical Model for the Motion of a Towed Pipeline Bundle
• The Kaczmarz algorithm, row action methods, and statistical learning algorithms
• Metric-Constrained Optimization for Graph Clustering Algorithms
• Quantile-based iterative methods for corrupted systems of linear equations
• Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions
• On the behaviour of the underrelaxed Hildreth's row-action method for computing projections onto Polyhedra
• A greedy randomized average block projection method for linear feasibility problems
• Survey of a class of iterative row-action methods: the Kaczmarz method
• Extending linear relaxation for non-square matrices and soft constraints

Describes a project that uses

Uses Software

• Matlab
• QOCA
• linprog
• HiRise
• Cassowary

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)