×

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
PDFBibTeX XMLCite
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.: 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 University Press Cambridge
[4] Hansen, E., Global optimization using interval analysis (1992), Marcel Dekker Inc: Marcel Dekker Inc New York · Zbl 0762.90069
[5] Ratschek, H.; Rokne, J., Interval methods, (Horst, R.; Pardalos, P. M., Handbook of global optimization (1995), Kluwer Academic Publisher: Kluwer Academic Publisher Netherlands), 751-828 · Zbl 0832.90109
[6] Lebbah Y. ICOS (interval constraints solver). WWW-document, \(2003. \langle;\) http://www-sop.inria.fr/coprin/ylebbah/icos \(\rangle;\).; Lebbah Y. ICOS (interval constraints solver). WWW-document, \(2003. \langle;\) http://www-sop.inria.fr/coprin/ylebbah/icos \(\rangle;\).
[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.; 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.; 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.; 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: 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: Prentice-Hall Englewood Cliffs, NJ · Zbl 0176.13301
[16] Hickey, T. J., CLIP: A CLP intervals dialect for metalevel constraint solving, (Proceedings of PADL ‘2000 international workshop on practical aspects of declarative languages, Lecture notes on computer science, vol. 1753 (2000), Springer: Springer Boston), 200-214
[17] Ceberio, M.; Granvilliers, L., Solving nonlinear equations by abstraction, Gaussian elimination, and interval methods, (Alessandro, A., Proceedings of frontiers of combining systems, fourth international workshop, FroCoS 2002. Lecture notes on artificial intelligence, vol. 2309 (2002), Springer: Springer Italy), 117-131 · Zbl 1057.68110
[18] Buchberger, B., Grobner bases: an algorithmic method in polynomial ideal theory, (Bose, N. K., Mutidimensional systems theory (1985), D. Reidel Publishing Co: D. Reidel Publishing Co Dordrecht), 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, (Proceedings of the 2005 ACM symposium on applied computing (2005), ACM Press: ACM Press New York, USA), 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.; 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.; 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.; 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: MIT Press London, England
[30] COCONUT \(\langle;\) http://www.mat.univie.ac.at/ neum/glopt/coconut/benchmark.html \(\rangle;\), 2005.; COCONUT \(\langle;\) http://www.mat.univie.ac.at/ neum/glopt/coconut/benchmark.html \(\rangle;\), 2005.
[31] COPRIN \(\langle;\) http://www-sop.inria.fr/coprin/logiciels/ALIAS/Benches/\( \rangle;\), 2004.; COPRIN \(\langle;\) http://www-sop.inria.fr/coprin/logiciels/ALIAS/Benches/\( \rangle;\), 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.; 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.; 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.; 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. 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.