Abstract
This article introduces a new filtering algorithm for handling systems of quadratic equations and inequations. Such constraints are widely used to model distance relations in numerous application areas ranging from robotics to chemistry. Classical filtering algorithms are based upon local consistencies and thus, are often unable to achieve a significant pruning of the domains of the variables occurring in quadratic constraint systems. The drawback of these approaches comes from the fact that the constraints are handled independently. We introduce here a global filtering algorithm that works on a tight linear relaxation of the quadratic constraints. The Simplex algorithm is then used to narrow the domains. Since most implementations of the Simplex work with floating point numbers and thus, are unsafe, we provide a procedure to generate safe linearizations. We also exploit a procedure provided by Neumaier and Shcherbina to get a safe objective value when calling the Simplex algorithm. With these two procedures, we prevent the Simplex algorithm from removing any solution while filtering linear constraint systems. Experimental results on classical benchmarks show that this new algorithm yields a much more effective pruning of the domains than local consistency filtering algorithms.
Similar content being viewed by others
References
Al-Khayyal, F. (1990). Jointly constrained biconvex programming and related problems: An overview. Comput. Math. Appl. 19: 53–62.
Al-Khayyal, F., & Falk, J. (1983). Jointly constrained biconvex programming. Math. Oper. Res. 8: 273–286.
Audet, C., Hansen, P., Jaumard, B., & Savard, G. (2000). Branch and cut algorithm for nonconvex quadratically constrained quadratic programming. Math. Prog. 87(1): 131–152.
Bazarra, M., Sherali, H., & Shetty, C. (1993). Nonlinear Programming: Theory and Algorithms. John Wiley & Sons.
Bellido, A. (1992). Construction of iteration functions for the simultaneous computation of the solutions of equations and algebraic systems. Numer. Algorithms 6(3–4): 317–351.
Benhamou, F., McAllester, D., & Van-Hentenryck P. (1994). CLP(intervals) revisited. In Proceedings of the International Symposium on Logic Programming, pages 124–138.
COCONUT. (2002). A benchmark for global optimization and constraint satisfaction. Technical report, WWW-document (2002). http://www.mat.univie.ac.at/neum/glopt/coconut/benchmark.html.
Cox, D., Little, J., & O’Shea, D. (1997). Ideals, Varieties, and Algorithms. 2nd edition. New York: Springer-Verlag.
Davis, E. (1987). Constraint propagation with interval labels. J. Artif. Intell. 32: 281–331.
Didrit, O. (1997). Analyse par intervalles pour l’automatique: Résolution globale et garantie de problèmes non linéaires en robotique et en commande robuste. Ph.D. thesis, Université Parix XI Orsay.
Faltings, B. (1994). Arc consistency for continuous variables. J. Artif. Intell. 60(2): 363–376.
Granvilliers, L. (2004). RealPaver, Version 0.4, http://www.sciences.univernantes.fr/info/perso/permanents/granvil/realpaver/main.html.
Hansen, E. R. (1992). Global Optimization Using Interval Analysis. New York: Marcel Dekker.
Collavizza, H., Delobel, F., & Rueher, M. (1999). Comparing partial consistencies. Reliab. Comput. 5(3): 213–228.
IEEE-754. (1985). IEEE Standard for Binary Floating Point Arithmetic. ANSI/IEEE, New York, Std 754-1985 edition.
Ilog (ed.) (2000a). ILOG CPLEX 7.0, Reference Manual. Ilog.
Ilog (ed.) (2000b). ILOG Solver 5.0, Reference Manual. Ilog.
Jermann, C., Trombettoni, G., Neveu, B., & Rueher, M. (2000). A constraint programming approach for solving rigid geometric systems. In Proceedings of CP’00: Sixth International Conference on “Principles and Practice of Constraint Programming”. Singapore, pages 233–248.
Kearfott, R. B. (1996). Rigorous Global Search: Continous Problems. Kluwer Academic Publishers Group.
Lebbah, Y. (1999). Contibution à la résolution de contraintes par consistance forte. Ph.D. thesis, Ecole des Mines de Nantes, France.
Lebbah, Y., & Lhomme, O. (2002). Accelerating filtering techniques for numeric CSPs’. Artif. Intill. 139(1): 109–132.
Lebba, Y., Michel, C., Rueher, M., Daney, D., & Merlet, J. (2205). Efficient and safe global constraints for handling numerical constraint system. SIAM journal of Numerical Analysis p. to appear.
Lebbah, Y., Rueher, M., & Michel, C. (2002). A global filtering algorithm for handling systems of quadratic equations and inequations. Proc. CP’2002, Lect. Notes Comput. Sci. 2470: 109–123.
Lhomme, O. (1993). Consistency techniques for numeric CSPs’. In Proceedings of IJCAI’93, pages 232–238.
Marti, P., & Rueher, M. (1995). A distributed cooperating constraints solving system. Int. J. Artif. Intell. Tools 4(1–2): 93–113.
McCormick, G. (1976). Computability of global solutions to factorable non-convex programs—Part I—Convex underestimating problems. Math. Prog. 10: 147–175.
Michel, C., Lebbah, Y., & Rueher, M. (2003). Safe embedding of the Simplex Algorithm in a CSP framework. In Proceedings of 5th Internatinal Workshop on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimisation Problems CPAIOR 2003, CRT, Université de Montréal, pages 210–220.
Neumaier, A., & Shcherbina, O. (2002). Safe bounds in linear and mixed-integer programming. Math. Prog A. 99: 283–296.
Puget, J., & Van-Hentenryck, P. (1998). A constraints satisfaction approach to a circuit design problem. J. Glob. Optim. 13(1): 75–93.
Sherali, H., & Adams, W. (1999). A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic Publishing.
Sherali, H., & Tuncbilek, C. (1992). A global optimization algorithm for polynomial using a reformulation-linearization technique. J. Glob. Optim. 7: 1–31.
Van-Hentenryck, P., Michel, L., & Deville, Y. (1997). Numerica: a Modelling language for Global Optiization. MIT Press.
Wunderlings, R. (1996). Paralleler und Objektorientierter Simplex-Algorithmus (in German). Ph.D. thesis, Berlin.
Author information
Authors and Affiliations
Corresponding author
Additional information
*This article is an extended version of [23].
Rights and permissions
About this article
Cite this article
Lebbah, Y., Michel, C. & Rueher, M. A Rigorous Global Filtering Algorithm for Quadratic Constraints*. Constraints 10, 47–65 (2005). https://doi.org/10.1007/s10601-004-5307-7
Issue Date:
DOI: https://doi.org/10.1007/s10601-004-5307-7