×

Efficient interval partitioning-local search collaboration for constraint satisfaction. (English) Zbl 1278.90185

Summary: A cooperative solution methodology that integrates interval partitioning \((IP)\) algorithms with a local search, feasible sequential quadratic programming \((FSQP)\), is presented as a technique to enhance the solving of continuous constraint satisfaction problems (continuous CSP). \(FSQP\) is invoked using a special search tree management system developed to increase search efficiency in finding feasible solutions.
In this framework, we introduce a new symbolic method for selecting the subdivision directions that targets immediate reduction of the uncertainty related to constraint infeasibility in child boxes. This subdivision method is compared against two previously established partitioning rules (also parallelized in a similar manner) used in the interval literature and shown to improve the efficiency of \(IP\). Further, the proposed tree management system is compared with tree management approaches that are classically used in \(IP\). The whole method is compared with published results of established symbolic-numeric methods for solving CSP on a number of state-of-the-art benchmarks.

MSC:

90B40 Search theory
90C20 Quadratic programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Neumaier, A.; Shcherbina, O.; Huyer, W.; Vinko, T., A comparison of complete global optimization solvers, Mathematical programming, 103, 335-356, (2005) · Zbl 1099.90001
[2] Alefeld, G.; Herzberger, J., Introduction to interval computations, (1983), Academic Press Inc. New York, USA
[3] Neumaier, A., Interval methods for systems of equations encyclopedia of mathematics and its applications, vol. 37, (1990), Cambridge University Press Cambridge
[4] Hansen, E., Global optimization using interval analysis, (1992), Marcel Dekker Inc New York · Zbl 0762.90069
[5] Ratschek, H.; Rokne, J., Interval methods, (), 751-828 · Zbl 0832.90109
[6] Lebbah Y. ICOS (interval constraints solver). WWW-document, 2003. \(\langle\)http://www-sop.inria.fr/coprin/ylebbah/icos⟩.
[7] Panier, E.R.; Tits, A.L., On combining feasibility, descent and superlinear convergence in inequality constrained optimization, Mathematical programming, 59, 261-276, (1993) · Zbl 0794.90068
[8] Zhou, J.L.; Tits, A.L., An SQP algorithm for finely discretized continuous minimax problems and other minimax problems with many objective functions, SIAM journal on optimization, 6, 461-487, (1996) · Zbl 0858.49027
[9] Lawrence CT, Zhou JL, Tits AL. User’s guide for CFSQP version 2.5: a code for solving (large scale) constrained nonlinear (minimax) optimization problems, generating iterates satisfying all inequality constraints. Institute for Systems Research, University of Maryland, College Park, MD, 1997.
[10] Yamamura, K.; Kawata, H.; Tokue, A., Interval solution of nonlinear equations using linear programming, BIT numerical mathematics, 38, 186-199, (1998) · Zbl 0908.65038
[11] Lebbah Y, Rueher M, Michel C. A global filtering algorithm for handling systems of quadratic equations and inequalities. CP2003, Lecture notes on computer science, vol. 2470. 2003. p. 109-213.
[12] Stevenson D. IEEE standard for binary floating point arithmetic. IEEE/ANSI 754-1985, Floating Point Working Group, Microprocessor Standards Sub-Committee, 1985.
[13] Goldberg, D.E., Genetic algorithms in search, optimization and machine learning, (1989), Addison-Wesley Reading, MA · Zbl 0721.68056
[14] Jeavons, P.; Cohen, D.; Cooper, M., Constraint, consistency and closure, Artificial intelligence, 101, 251-265, (1998) · Zbl 0909.68076
[15] Moore, R.E., Interval analysis, (1966), Prentice-Hall Englewood Cliffs, NJ · Zbl 0176.13301
[16] Hickey, T.J., CLIP: A CLP intervals dialect for metalevel constraint solving, (), 200-214
[17] Ceberio, M.; Granvilliers, L., Solving nonlinear equations by abstraction, Gaussian elimination, and interval methods, (), 117-131 · Zbl 1057.68110
[18] Buchberger, B., Grobner bases: an algorithmic method in polynomial ideal theory, (), 184-232 · Zbl 0587.13009
[19] Rump, S.M., On the solution of interval linear systems, Computing, 47, 337-353, (1992) · Zbl 0753.65030
[20] Chabert, G.; Trombettoni, G.; Neveu, B., Box-set consistency for interval based constraint problems. symposium on applied computing SAC 2005, (), 1439-1443
[21] Kearfott, R.B.; Manuel, N.I.I.I., INTBIS: a portable interval Newton/bisection package, ACM transactions on mathematical software, 16, 152-157, (1990) · Zbl 0900.65152
[22] Korf, R.E., Depth-first iterative deepening: an optimal admissible tree search, Artificial intelligence, 27, 97-109, (1985) · Zbl 0573.68030
[23] Benhamou F, McAllester D, Van Hentenryck P. CLP (intervals) revisited. Proceedings of ILPS’94, international logic programming symposium, 1994. p. 124-38.
[24] Kearfott, R.B., Decomposition of arithmetic expressions to improve the behaviour of interval iteration for nonlinear systems, Computing, 47, 169-191, (1991) · Zbl 0739.65049
[25] Smith, E.M.B.; Pantelides, C.C., Symbolic reformulation/spatial branch and bound algorithm for the global optimization of nonconvex minlps, Computers and chemical engineering, 25, 1399-1401, (2001)
[26] Sahinidis NV. Global optimization and constraint satisfaction: the branch and reduce approach. Leture notes on computer science, vol. 2861. 2003. p. 1-16. · Zbl 1255.90102
[27] Tawarmalani, M.; Sahinidis, N.V., Global optimization of mixed-integer nonlinear programs: a theoretical and computational study, Mathematical programming, 99, 563-591, (2004) · Zbl 1062.90041
[28] Merlet J-P. ALIAS: an interval analysis based library for solving and analyzing system of equations. Séminaire Systèmes et équations algébriques, Toulouse, Automation, 2000. p. 1964-1969.
[29] Van-Hentenryck, P.; Michel, L.; Deville, Y., Numerica: a modeling language for global optimization, (1997), MIT Press London, England
[30] COCONUT \(\langle\)http://www.mat.univie.ac.at/ neum/glopt/coconut/benchmark.html⟩, 2005.
[31] COPRIN \(\langle\)http://www-sop.inria.fr/coprin/logiciels/ALIAS/Benches/⟩, 2004.
[32] Dietmaier P. The Stewart-Gough platform of general geometry can have 40 real postures. Proceedings of ARK, Strobl, Austria; 1998. p. 7-16. · Zbl 0953.70006
[33] Knuppel, O., PROFIL/BIAS—a fast interval library, Computing, 53, 277-287, (1994) · Zbl 0808.65055
[34] Shcherbina O, Neumaier A, Sam-Haroud D, Vu X-H, Nguyen T-V. Benchmarking global optimization and constraint satisfaction codes. Global optimization and constraint satisfaction: first international workshop on global constraint optimization and constraint satisfaction, COCOS 2002, Valbonne-Sophia Antipolis, France; 2002. · Zbl 1296.90004
[35] Schichl H, Neumaier A. Interval analysis on directed acyclic graphs for global optimization. Institut for Mathematik; Universitat Wien, Austria: 2003. · Zbl 1094.65061
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.