Article

Hierarchical nonlinear constraint satisfaction

Author:

Hiroshi HosobeAuthors Info & Claims

SAC '04: Proceedings of the 2004 ACM symposium on Applied computing

Pages 16 - 20

https://doi.org/10.1145/967900.967907

Published: 14 March 2004 Publication History

Abstract

Constraint programming is a method of problem solving that allows declarative specification of relations among objects. It is important to allow preferences of constraints since it is often difficult for programmers to specify all constraints without conflicts. In this paper, we propose a numerical method for solving nonlinear constraints with hierarcical preferences (i.e., constraint hierarchies) in a least-squares manner. This method finds sufficiently precise local optimal solutions by appropriately processing hierarchical preferences of constraints. To evaluate the effectiveness of our method, we present experimental results obtained with a prototype constraint solver.

References

[1]

G. J. Badros, A. Borning, and P. J. Stuckey. The Cassowary linear arithmetic constraint solving algorithm. ACM Trans. Comput.-Human Interact., 8(4):267--306, 2001.]]

Digital Library

[2]

F. Benhamou and M. Ceberio. Soft constraints: A unifying framework applied to continuous soft constraints. In Proc. Workshop of the ERCIM Working Group on Constraints and the CoLogNET Area on Constraint and Logic Programming, 2003.]]

[3]

S. Bistarelli, U. Montanari, and F. Rossi. Semiring-based constraint solving and optimization. J. ACM, 44(2):201--236, 1997.]]

Digital Library

[4]

A. Björck. Numerical Methods for Least Squares Problems. SIAM, 1996.]]

[5]

A. Borning, B. Freeman-Benson, and M. Wilson. Constraint hierarchies. Lisp Symbolic Comput., 5(3):223--270, 1992.]]

Digital Library

[6]

A. Borning, K. Marriott, P. Stuckey, and Y. Xiao. Solving linear arithmetic constraints for user interface applications. In Proc. ACM UIST, pages 87--96, 1997.]]

Digital Library

[7]

R. Fletcher. Practical Methods of Optimization. Wiley, 2nd edition, 1987.]]

Digital Library

[8]

B. N. Freeman-Benson, J. Maloney, and A. Borning. An incremental constraint solver. Comm. ACM, 33(1):54--63, 1990.]]

Digital Library

[9]

E. C. Freuder and R. J. Wallace. Partial constraint satsfaction. Artif. Intell., 58:21--70, 1992.]]

Digital Library

[10]

M. Gulliksson, I. Söderkvist, and P.-Å. Wedin. Algorithms for constrined and weighted nonlinear least squares. SIAM J. Optim., 7(1):208--224, 1997.]]

Digital Library

[11]

M. Gulliksson and P.-Å. Wedin. Modifying the QR-decomposition to constrained and weighted linear least squares. SIAM J. Matrix Anal. Appl., 13(4):1298--1313, 1992.]]

Digital Library

[12]

H. Hosobe. A scalable linear constraint solver for user interface construction. In Principles and Practice of Constraint Programming---CP2000, volume 1894 of LNCS, pages 218--232. Springer, 2000.]]

Digital Library

[13]

H. Hosobe. A modular geometric constraint solver for user interface applications. In Proc. ACM UIST, pages 91--100, 2001.]]

Digital Library

[14]

N. Hurst, K. Marriott, and P. Moulder. Dynamic approximation of complex graphical constraints by linear constraints. In Proc. ACM UIST, pages 191--200, 2002.]]

Digital Library

[15]

G. A. Kramer. A geometric constraint engine. Artif. Intell., 58(1--3):327--360, 1992.]]

Digital Library

[16]

K. Marriott and S. S. Chok. QOCA: A constraint solving toolkit for interactive graphical applications. Constraints, 7(3--4):229--254, 2002.]]

Digital Library

[17]

J. C. Owen. Algebraic solution for geometry from dimensional constraints. In Proc. ACM Solid Modeling, pages 397--407, 1991.]]

Digital Library

Cited By

Hosobe H(2015)A Hierarchical Method for Solving Soft Nonlinear ConstraintsProcedia Computer Science10.1016/j.procs.2015.08.42262(378-384)Online publication date: 2015
https://doi.org/10.1016/j.procs.2015.08.422
Skubch HOssowski SLecca P(2012)Solving non-linear arithmetic constraints in soft realtime environmentsProceedings of the 27th Annual ACM Symposium on Applied Computing10.1145/2245276.2245293(67-73)Online publication date: 26-Mar-2012
https://dl.acm.org/doi/10.1145/2245276.2245293
Christie MOlivier PNormand J(2008)Camera Control in Computer GraphicsComputer Graphics Forum10.1111/j.1467-8659.2008.01181.x27:8(2197-2218)Online publication date: 21-Nov-2008
https://doi.org/10.1111/j.1467-8659.2008.01181.x

Hierarchical nonlinear constraint satisfaction
1. Information systems
  1. Data management systems
    1. Database administration
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Constraint Hierarchies as Semiring-Based CSPs
ICTAI '09: Proceedings of the 2009 21st IEEE International Conference on Tools with Artificial Intelligence

Constraints provide an effective means for the high-level modeling and reasoning of various problems. In particular, soft constraints are useful since they treat over-constrained problems that naturally arise in real-life applications. Therefore, ...
Solving conditional and composite constraint satisfaction problems
SAC '07: Proceedings of the 2007 ACM symposium on Applied computing

Constraint Satisfaction Problems (CSPs) have been widely used to solve combinatorial problems. In order to deal with dynamic CSPs where the information regarding any possible change is known a priori and can thus be enumerated beforehand, conditional ...
A Foundation of Solution Methods for Constraint Hierarchies

Constraint hierarchies provide a framework for soft constraints, and have been applied to areas such as artificial intelligence, logic programming, and user interfaces. In this framework, constraints are associated with hierarchical preferences or ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SAC '04: Proceedings of the 2004 ACM symposium on Applied computing

March 2004

1733 pages

ISBN:1581138121

DOI:10.1145/967900

Conference Chair:
Hisham M. Haddad
Kennesaw State University
,
Program Chairs:
Andrea Omicini
Università degli Studi di Bologna a Cesena
,
Roger L. Wainwright
University of Tulsa
,
Publications Chair:
Lorie M. Liebrock
New Mexico Institute of Mining and Technology

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 March 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SAC04

Sponsor:

SIGAPP

SAC04: The 2004 ACM Symposium on Applied Computing

March 14 - 17, 2004

Nicosia, Cyprus

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
325
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hosobe H(2015)A Hierarchical Method for Solving Soft Nonlinear ConstraintsProcedia Computer Science10.1016/j.procs.2015.08.42262(378-384)Online publication date: 2015
https://doi.org/10.1016/j.procs.2015.08.422
Skubch HOssowski SLecca P(2012)Solving non-linear arithmetic constraints in soft realtime environmentsProceedings of the 27th Annual ACM Symposium on Applied Computing10.1145/2245276.2245293(67-73)Online publication date: 26-Mar-2012
https://dl.acm.org/doi/10.1145/2245276.2245293
Christie MOlivier PNormand J(2008)Camera Control in Computer GraphicsComputer Graphics Forum10.1111/j.1467-8659.2008.01181.x27:8(2197-2218)Online publication date: 21-Nov-2008
https://doi.org/10.1111/j.1467-8659.2008.01181.x

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents