Abstract
Many mixed-integer constraint satisfaction problems and global optimization problems contain some variables with unbounded domains. Their solution by branch and bound methods to global optimality poses special challenges as the search region is infinitely extended. Many usually strong bounding methods lose their efficiency or fail altogether when infinite domains are involved. Most implemented branch and bound solvers add artificial bounds to make the problem bounded, or require the user to add these. However, if these bounds are too small, they may exclude a solution, while when they are too large, the search in the resulting huge but bounded region may be very inefficient. Moreover, if the global solver must provide a rigorous guarantee (as for the use in computer-assisted proofs), such artificial bounds are not permitted without justification by proof.
We developed methods based on compactification and projective geometry as well as asymptotic analysis to cope with the unboundedness in a rigorous manner. Based on projective geometry we implemented two different versions of the basic idea, namely (i) projective constraint propagation, and (ii) projective transformation of the variables, in the rigorous global solvers COCONUT and GloptLab. Numerical tests demonstrate the capability of the new technique, combined with standard pruning methods, to rigorously solve unbounded global problems. In addition, we present a generalization of projective transformation based on asymptotic analysis.
Compactification and projective transformation, as well as asymptotic analysis, are fruitless in discrete situations but they can very well be applied to compute bounded relaxations, and we will present methods for doing that in an efficient manner.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Benhamou, F., Goualard, F.: Universally Quantified Interval Constraints. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 67–82. Springer, Heidelberg (2000)
Benhamou, F., Goualard, F., Granvilliers, L., Puget, J.F.: Revising Hull and Box Consistency. In: Proceedings of the International Conference on Logic Programming (ICLP 1999), Las Cruces, USA, pp. 230–244 (1999)
Benhamou, F., Older, W.J.: Applying Interval Arithmetic to Real, Integer and Boolean Constraints. Journal of Logic Programming, 32–81 (1997)
Berz, M., Makino, K.: Verified integration of odes and flows using differential algebraic methods on high-order taylor models. Reliable Computing 4, 361–369 (1998)
Berz, M.: COSY INFINITY version 8 reference manual. Technical report, National Superconducting Cyclotron Lab., Michigan State University, East Lansing, Mich., MSUCL–1008 (1997)
Domes, F.: Gloptlab-a configurable framework for solving continuous, algebraic CSPs. In: IntCP, Int. WS on Interval Analysis, Constraint Propagation, Applications, at CP Conference, pp. 1–16 (2009)
Domes, F.: Gloptlab: a configurable framework for the rigorous global solution of quadratic constraint satisfaction problems. Optimization Methods & Software 24(4-5), 727–747 (2009)
Domes, F., Neumaier, A.: Verified global optimization with gloptlab. PAMM 7(1), 1020101–1020102 (2008)
Eiermann, M.C.: Adaptive Berechnung von Integraltransformationen mit Fehlerschranken. PhD thesis, Institut für Angewandte Mathematik der Albert–Ludwigs–Universität Freiburg im Breisgau (October 1989)
Granvilliers, L., Goualard, F., Benhamou, F.: Box Consistency through Weak Box Consistency. In: Proceedings of the 11th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 1999), pp. 373–380 (November 1999)
Griewank, A., Corliss, G.F.: Automatic Differentiation of Algorithms. SIAM Publications, Philadelphia (1991)
Hansen, E.: Global Optimization using Interval Analysis. Marcel Dekker, New York (1992)
Jaulin, L., Kieffer, M., Didrit, O., Walter, E.: Applied Interval Analysis, 1st edn. Springer (2001)
Kearfott, R.: Decomposition of arithmetic expressions to improve the behavior of interval iteration for nonlinear systems. Computing 47(2), 169–191 (1991)
McCormick, G.: Computability of global solutions to factorable nonconvex programs: Part iconvex underestimating problems. Mathematical Programming 10(1), 147–175 (1976)
Moore, R.E.: Interval Arithmetic and Automatic Error Analysis in Digital Computing. PhD thesis, Appl. Math. Statist. Lab. Rep. 25. Stanford University (1962)
Moore, R.E.: Interval Analysis. Prentice-Hall, Englewood Cliffs (1966)
Neumaier, A.: Interval Methods for Systems of Equations. Cambridge University Press, Cambridge (1990)
Neumaier, A.: Taylor forms - use and limits. Reliable Computing 9, 43–79 (2002)
Neumaier, A.: Complete search in continuous global optimization and constraint satisfaction. Acta Numerica 13(1), 271–369 (2004)
Ninin, J., Messine, F., Hansen, P.: A reliable affine relaxation method for global optimization (2010); Optimzation Online
Ryoo, H., Sahinidis, N.: A branch-and-reduce approach to global optimization. Journal of Global Optimization 8(2), 107–138 (1996)
Schichl, H.: Global optimization in the COCONUT project. In: Alt, R., Frommer, A., Kearfott, R.B., Luther, W. (eds.) Numerical Software with Result Verification. LNCS, vol. 2991, pp. 243–249. Springer, Heidelberg (2004)
Schichl, H., Markót, M.C., et al.: The COCONUT Environment. Software, http://www.mat.univie.ac.at/coconut-environment
Schichl, H., Markót, M.C.: Algorithmic differentiation techniques for global optimization in the coconut environment. Optimization Methods and Software 27(2), 359–372 (2012)
Schichl, H., Neumaier, A.: Exclusion regions for systems of equations. SIAM Journal on Numerical Analysis 42(1), 383–408 (2004)
Schichl, H., Neumaier, A.: Interval analysis on directed acyclic graphs for global optimization. Journal of Global Optimization 33(4), 541–562 (2005)
Shcherbina, O., Neumaier, A., Sam-Haroud, D., Vu, X.H., Nguyen, T.V.: Benchmarking global optimization and constraint satisfaction codes. In: Bliek, C., Jermann, C., Neumaier, A. (eds.) COCOS 2002. LNCS, vol. 2861, pp. 211–222. Springer, Heidelberg (2003)
Silaghi, M.-C., Sam-Haroud, D., Faltings, B.V.: Search Techniques for Non-linear Constraint Satisfaction Problems with Inequalities. In: Stroulia, E., Matwin, S. (eds.) AI 2001. LNCS (LNAI), vol. 2056, pp. 183–193. Springer, Heidelberg (2001)
Stolfi, J., Andrade, M., Comba, J., Van Iwaarden, R.: Affine arithmetic: a correlation-sensitive variant of interval arithmetic, Web document (1994)
Van Hentenryck, P.: Numerica: A Modeling Language for Global Optimization. In: Proceedings of IJCAI 1997 (1997)
Vu, X.H., Sam-Haroud, D., Silaghi, M.C.: Numerical Constraint Satisfaction Problems with Non-isolated Solutions. In: Bliek, C., Jermann, C., Neumaier, A. (eds.) COCOS 2002. LNCS, vol. 2861, pp. 194–210. Springer, Heidelberg (2003)
Vu, X., Schichl, H., Sam-Haroud, D.: Using directed acyclic graphs to coordinate propagation and search for numerical constraint satisfaction problems. In: 16th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2004, pp. 72–81. IEEE (2004)
Vu, X., Schichl, H., Sam-Haroud, D.: Interval propagation and search on directed acyclic graphs for numerical constraint solving. Journal of Global Optimization 45(4), 499–531 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schichl, H., Neumaier, A., Markót, M.C., Domes, F. (2013). On Solving Mixed-Integer Constraint Satisfaction Problems with Unbounded Variables. In: Gomes, C., Sellmann, M. (eds) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2013. Lecture Notes in Computer Science, vol 7874. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38171-3_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-38171-3_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38170-6
Online ISBN: 978-3-642-38171-3
eBook Packages: Computer ScienceComputer Science (R0)