Hierarchical nonlinear constraint satisfaction

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: Greg J. Badros , Alan Borning , Peter J. Stuckey, The Cassowary linear arithmetic constraint solving algorithm, ACM Transactions on Computer-Human Interaction (TOCHI), v.8 n.4, p.267-306, December 2001 [doi>10.1145/504704.504705]
• 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: Stefano Bistarelli , Ugo Montanari , Francesca Rossi, Semiring-based constraint satisfaction and optimization, Journal of the ACM (JACM), v.44 n.2, p.201-236, March 1997 [doi>10.1145/256303.256306]
• 4: A. Björck. Numerical Methods for Least Squares Problems. SIAM, 1996.
• 5: Alan Borning , Bjorn Freeman-Benson , Molly Wilson, Constraint hierarchies, Lisp and Symbolic Computation, v.5 n.3, p.223-270, Sept. 1992 [doi>10.1007/BF01807506]
• 6: Alan Borning , Kim Marriott , Peter Stuckey , Yi Xiao, Solving linear arithmetic constraints for user interface applications, Proceedings of the 10th annual ACM symposium on User interface software and technology, p.87-96, October 14-17, 1997, Banff, Alberta, Canada [doi>10.1145/263407.263518]
• 7: R. Fletcher, Practical methods of optimization; (2nd ed.), Wiley-Interscience, New York, NY, 1987
• 8: Bjorn N. Freeman-Benson , John Maloney , Alan Borning, An incremental constraint solver, Communications of the ACM, v.33 n.1, p.54-63, Jan. 1990 [doi>10.1145/76372.77531]
• 9: Eugene C. Freuder , Richard J. Wallace, Partial constraint satisfaction, Artificial Intelligence, v.58 n.1-3, p.21-70, Dec. 1992 [doi>10.1016/0004-3702(92)90004-H]
• 10: Mårten Gulliksson , Inge Söderkvist , Per-Åke Wedin, Algorithms for Constrained and Weighted Nonlinear Least Squares, SIAM Journal on Optimization, v.7 n.1, p.208-224, 1997 [doi>10.1137/S1052623493248809]
• 11: Mårten Gullisson , Per-Åke Wedin, Modifying the QR-decomposition to constrained and weighted line linear last squares, SIAM Journal on Matrix Analysis and Applications, v.13 n.4, p.1298-1313, Oct. 1992 [doi>10.1137/0613079]
• 12: Hiroshi Hosobe, A Scalable Linear Constraint Solver for User Interface Construction, Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming, p.218-232, September 18-21, 2000
• 13: Hiroshi Hosobe, A modular geometric constraint solver for user interface applications, Proceedings of the 14th annual ACM symposium on User interface software and technology, November 11-14, 2001, Orlando, Florida [doi>10.1145/502348.502362]
• 14: Nathan Hurst , Kim Marriott , Peter Moulder, Dynamic approximation of complex graphical constraints by linear constraints, Proceedings of the 15th annual ACM symposium on User interface software and technology, October 27-30, 2002, Paris, France [doi>10.1145/571985.572012]
• 15: Glenn A. Kramer, A geometric constraint engine, Artificial Intelligence, v.58 n.1-3, p.327-360, Dec. 1992 [doi>10.1016/0004-3702(92)90012-M]
• 16: Kim Marriott , Sitt Sen Chok, QOCA: A Constraint Solving Toolkit for Interactive Graphical Applications, Constraints, v.7 n.3-4, p.229-254, July-October 2002 [doi>10.1023/A:1020513316058]
• 17: J. C. Owen, Algebraic solution for geometry from dimensional constraints, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, p.397-407, June 05-07, 1991, Austin, Texas, United States [doi>10.1145/112515.112573]

INDEX TERMS

Keywords:
constraint hierarchies, constraint satisfaction, least squares, nonlinear constraints