Using constraint techniques for a safe and fast implementation of optimality-based reduction

ABSTRACT

Optimality-based reduction attempts to take advantage of the known bounds of the objective function to reduce the domain of the variables, and thus to speed up the search of a global optimum. However, the basic algorithm is unsafe, and thus, the overall process may no longer be complete and may not reach the actual global optimum. Recently, Kearfott has proposed a safe implementation of optimality-based reduction. Unfortunately, his method suffers from some limitations and is rather slow. In this paper, we show how constraint programming filtering techniques can be used to implement optimality-based reduction in a safe and efficient way.

REFERENCES

• 1: C. Audet. Optimisation Globale Structurée: Propriétés, Équivalences et Résolution. PhD thesis, École Polytechnique de Montréal, Quebec, 1997.
• 2: V. Balakrishnan and S. P. Boyd. Global optimization in control system analysis and design. In C. Leondes, editor, Control and Dynamic Systems: Advances in Theory and Applications, volume 53. Academic Press, New York, New York, 1992.
• 3: M. S. Bazaraa, H. D. Sherali, and C. M. Shetty. Nonlinear Programming : Theory and Algorithms. John Wiley & Sons, 1993.
• 4: F. Benhamou , D. McAllester , P. van Hentenryck, CLP(intervals) revisited, Proceedings of the 1994 International Symposium on Logic programming, p.124-138, November 1994, Symposia, Melbourne
• 5: F. Benhamou and W. Older. Applying interval arithmetic to real, integer and boolean constraints. Journal of Logic Programming, pages 1--24, 1997.
• 6: Glencora Borradaile , Pascal Van Hentenryck, Safe and tight linear estimators for global optimization, Mathematical Programming: Series A and B, v.102 n.3, p.495-517, April 2005 [doi>10.1007/s10107-004-0533-8]
• 7: J. G. Cleary. Logical arithmetic. Future Computing Systems, pages 125--149, 1987.
• 8: H. Collavizza, F. Delobel, and M. Rueher. Comparing partial consistencies. Reliable Computing, pages 213--228, 1999.
• 9: C. A. Floudas. Deterministic global optimization in design, control, and computational chemistry. In IMA Proceedings: Large Scale Optimization with Applications. Part II: Optimal Design and Control, pages 129--184, 1997.
• 10: E. R. Hansen. Global Optimization Using Interval Analysis. Marcel Dekker, New York, 2004.
• 11: R. Horst and H. Tuy. Global Optimization: Deterministic Approches. Springer-Verlag, 1993.
• 12: R. B. Kearfott. Validated probing with linear relaxations, submitted to Journal of Global Optimization, 2005.
• 13: R. B. Kearfott. Discussion and empirical comparisons of linear relaxations and alternate techniques in validated deterministic global optimization, Journal of Optimization Methods and Software, pages 715--731, Oct. 2006.
• 14: Yahia Lebbah , Olivier Lhomme, Accelerating filtering techniques for numeric CSPs, Artificial Intelligence, v.139 n.1, p.109-132, July 2002 [doi>10.1016/S0004-3702(02)00194-7 ]
• 15: Yahia Lebbah , Claude Michel , Michel Rueher, An efficient and safe framework for solving optimization problems, Journal of Computational and Applied Mathematics, v.199 n.2, p.372-377, 15 February 2007 [doi>10.1016/j.cam.2005.08.037]
• 16: Yahia Lebbah , Claude Michel , Michel Rueher , David Daney , Jean-Pierre Merlet, Efficient and Safe Global Constraints for Handling Numerical Constraint Systems, SIAM Journal on Numerical Analysis, v.42 n.5, p.2076-2097, 2004 [doi>10.1137/S0036142903436174]
• 17: E. Lee and C. Mavroidis. Solving the geometric design problem of spatial 3R robot manipulators using polynomial homotopy continuation. Journal of Mechanical Design, 124(4):652--661, Dec. 2002.
• 18: O. Lhomme. Consistency techniques for numeric CSPs. In Proceedings of IJCAI'93, pages 232--238, Chambéry (France), 1993.
• 19: A. K. Mackworth. Consistency in networks of relations. Artificial Intelligence, pages 99--118, 1977.
• 20: C. Michel, Y. Lebbah, and M. Rueher. Safe embedding of the simplex algorithm in a CSP framework. In Proc. of CPAIOR 2003, Montréal, 2003.
• 21: M. Minoux. Mathematical Programming. Theory, Algorithms and Applications. Wiley, 1986.
• 22: B. A. Murtagh and M. A. Saunders. Minos 5.5 user's guide. Technical Report SOL 83--20R, Systems Optimization Laboratory, Dep. of Operations Research, Stanford University, July 1998.
• 23: A. Neumaier. Complete search in continuous global optimization and constraint satisfaction. Acta Numerica, 2004.
• 24: Arnold Neumaier , Oleg Shcherbina, Safe bounds in linear and mixed-integer linear programming, Mathematical Programming: Series A and B, v.99 n.2, p.283-296, March 2004 [doi>10.1007/s10107-003-0433-3]
• 25: H. S. Ryoo and N. V. Sahinidis. Global optimization of nonconvex NLPs and MINLPs with applications in process design. Computers Chemical Engineering, 19(5):551--566, 1995.
• 26: H. S. Ryoo and N. V. Sahinidis. A branch-and-reduce approach to global optimization. Journal of Global Optimization, pages 107--138, 1996.
• 27: D. Sam-Haroud and B. Faltings. Consistency techniques for continuous constraints. Constraints, 1(1/2):85--118, 1996.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

General Terms:
Algorithms, Reliability

Keywords:
constraint programming, global optimization, reliable computing