×

Extending linear relaxation for non-square matrices and soft constraints. (English) Zbl 1346.65013

Summary: 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.

MSC:

65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[2] Kunis, S.; Rauhut, H., Random sampling of sparse trigonometric polynomials, ii. Orthogonal matching pursuit versus basis pursuit, J. Found. Comput. Math., 8, 6, 737-763 (2008) · Zbl 1165.94314
[3] Anita, H. M., Numerical Methods for Scientist and Engineers (2002), Birkhauser
[4] Benzi, M., Preconditioning techniques for large linear systems: A survey, J. Comput. Phys., 182, 418-477 (2002) · Zbl 1015.65018
[5] Borning, A.; Freeman-Benson, B.; Wilson, M., Constraint hierarchies, Lisp Symb. Comput., 5, 3, 223-270 (1992)
[6] Chinneck, J. W., Fast heuristics for the maximum feasible subsystem problem, Inf. J. Comput., 210-223 (2001) · Zbl 1238.90093
[7] Badros, G. J.; Borning, A.; Stuckey, P. J., The cassowary linear arithmetic constraint solving algorithm, ACM Trans. Comput.-Hum. Interact., 8, 4, 267-306 (2001)
[8] Borning, A.; Marriott, K.; Stuckey, P.; Xiao, Y., Solving linear arithmetic constraints for user interface applications, (Proceedings of the 10th Annual ACM Symposium on User Interface Software and Technology. Proceedings of the 10th Annual ACM Symposium on User Interface Software and Technology, UIST’97 (1997), ACM), 87-96, URL: http://doi.acm.org/10.1145/263407.263518
[10] Marriott, K.; Chok, S. C.; Finlay, A., A tableau based constraint solving toolkit for interactive graphical applications, (Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming. Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming, CP’98 (1998), Springer: Springer London, UK), 340-354
[11] Jamil, N.; Chen, X.; Cloninger, A., Randomized hildreth’s algorithm with applications to soft constraints for user interface layout, J. Comput. Appl. Math., 288, 193-202 (2015) · Zbl 1326.65068
[16] Young, D. M., Iterative Solution of Large Linear Systems (1971), Academic Press · Zbl 0204.48102
[17] Datta, B. N., Numerical Linear Algebra and Applications (1995), Cole Publishing
[18] Saad, Y., Iterative Methods for Sparse Linear Systems, 112 (2003), SIAM: SIAM Philadelphia, PA
[19] Ruiz, D., A scaling algorithm to equilibrate both rows and columns norms in matrices, Tech. Rep. (2001)
[20] Duff, I. S.; Koster, J., On algorithms for permuting large entries to the diagonal of a sparse matrix, Tech. Rep. (1999) · Zbl 0979.05087
[21] Goffin, J. L., The relaxation method for solving systems of linear inequalities, Math. Oper. Res., 5, 3, 388-414 (1980) · Zbl 0442.90051
[22] Agmon, S., The relaxation method for linear inequalities, Canad. J. Math., 382-392 (1954) · Zbl 0055.35001
[23] Motzkin, T.; Schoenberg, I., The relaxation method for linear inequalities, Canad. J. Math., 393-404 (1954) · Zbl 0055.35002
[24] Burden, R. L.; Faires, J., Numerical Analysis (2005), Bob Pirtle
[25] Heath, M. T., Scientific Computing, An Introductory Survey (1997), The McGraw-Hill Companies · Zbl 0903.68072
[26] Foster, L. V., Modifications of the normal equations method that are numerically stable, In Numerical Linear Algebra, Digit. Signal Process. Parallel Algorithms, 501-512 (1991)
[27] Axelsson, O., Iterative Solution Methods (1996), Cambridge Uni. Press · Zbl 0845.65011
[28] Dantzig, G. B., (Linear Programming and Extensions. Linear Programming and Extensions, Princeton Landmarks in Mathematics (1998), Princeton Uni. Press: Princeton Uni. Press Princeton NJ, USA) · Zbl 0997.90504
[29] Taha, H. A., Operations Research: An Introduction (1992), Mcmillan Publishing · Zbl 0774.90026
[30] Saad, Y.; Schultz, M. H., Gmres: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 3, 856-869 (1986), URL: http://dx.doi.org/10.1137/0907058 · Zbl 0599.65018
[31] Hestenes, M. R.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand., 49, 409-436 (1952) · Zbl 0048.09901
[32] Golub, G.; Van Loan, C., Matrix Computations (1996), Johns Hopkins Uni. Press · Zbl 0865.65009
[33] Ding, F.; Chen, T., Iterative least-squares solutions of coupled sylvester matrix equations, Systems Control Lett., 54, 95-107 (2005) · Zbl 1129.65306
[34] Meseguer, P.; Bouhmala, N.; Bouzoubaa, T.; Irgens, M.; Sánchez, M., Current approaches for solving over-constrained problems, Constraints, 8, 1, 9-39 (2003) · Zbl 1039.68122
[35] Hosobe, H.; Matsuoka, S., A foundation of solution methods for constraint hierarchies, Constraints, 8, 1, 41-59 (2003) · Zbl 1039.68120
[38] Yoshioka, Y.; Masuda, H.; Furukawa, Y., A constrained least squares approach to interactive mesh deformation, (Proceedings of the IEEE International Conference on Shape Modeling and Applications 2006. Proceedings of the IEEE International Conference on Shape Modeling and Applications 2006, SMI’06 (2006), IEEE Computer Society: IEEE Computer Society Washington, DC, USA), 23-33, URL: http://dx.doi.org/10.1109/SMI.2006.1
[39] Hosobe, H., A scalable linear constraint solver for user interface construction, (Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming. Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming, CP’02 (2000), Springer: Springer London, UK), 218-232 · Zbl 1044.68768
[41] Freeman-Benson, J. M.; Borning, A., An incremental constraint solver, Commun. ACM, 33, 1, 54-63 (1990)
[42] Sannella, M., Skyblue: a multi-way local propagation constraint solver for user interface construction, (Proceedings of the 7th Annual ACM Symposium on User Interface Software and Technology. Proceedings of the 7th Annual ACM Symposium on User Interface Software and Technology, UIST’94 (1994), ACM), 137-146, URL: http://doi.acm.org/10.1145/192426.192485
[43] Hosobe, H.; Miyashita, K.; Takahashi, S.; Matsuoka, S.; Yonezawa, A., Locally simultaneous constraint satisfaction, (Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming. Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, PPCP’94 (1994), Springer: Springer London, UK), 51-62, URL: http://dl.acm.org/citation.cfm?id=645814.668743
[46] Li, C. M.; Manyà, F.; Mohamedou, N. O.; Planes, J., Exploiting cycle structures in max-sat, (SAT. SAT, Lecture Notes in Computer Science, 5584 (2009), Springer), 467-480 · Zbl 1247.68256
[53] Amaldi, E., From Finding Maximum Feasible Subsystems of Linear Systems to Feed-forward Neural Network Design (1994)
[54] Amaldi, E.; Bruglieri, M.; Casale, G., A two-phase relaxation-based heuristic for the maximum feasible subsystem problem, Comput. Oper. Res., 1465-1482 (2008) · Zbl 1278.90458
[55] Mangasarian, O., Misclassification minimization, J. Global Optim., 309-323 (1994) · Zbl 0814.90081
[56] Pfetsch, M., Branch and cut for the maximum feasible subsystemproblem, SIAM J. Optim., 21-38 (2008) · Zbl 1167.90018
[57] Chinneck, J. W.; Dravnieks, E., Locating minimal infeasible constraint sets in linear programs, ORSA J. Comput., 157-168 (1991) · Zbl 0755.90055
[59] Tamiz, M.; Mardle, S. J.; Jones, D. F., Resolving inconsistency in infeasible linear programmes, Tech. rep. (1995)
[60] Tamiz, M.; Mardle, S. J.; Jones, D. F., Detecting iis in infeasible linear programmes using techniques from goal programming, Comput. Oper. Res., 113-119 (1996) · Zbl 0868.90080
[62] Guieu, O.; Chinneck, J. W., Analyzing infeasible mixed-integer and integer linear programs, INFORMS J. Comput., 63-77 (1999) · Zbl 1034.90519
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.