Cited By
View all- Puranik YSahinidis N(2017)Domain reduction techniques for global NLP and MINLP optimizationConstraints10.1007/s10601-016-9267-522:3(338-376)Online publication date: 1-Jul-2017
Using constraint techniques for a safe and fast implementation of optimality-based reduction
Pages 326 - 331
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, and P. V. Hentenryck. Clp(intervals) revisited. In Proc. of the ISLP'94, pages 124--138, 1994.
[5]
F. Benhamou and W. Older. Applying interval arithmetic to real, integer and boolean constraints. Journal of Logic Programming, pages 1--24, 1997.
[6]
G. Borradaile and P. V. Hentenryck. Safe and tight linear estimators for global optimization. Mathematical Programming, 2005.
[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]
Y. Lebbah and O. Lhomme. Accelerating filtering techniques for numeric CSPs. Artificial Intelligence, 139(1):109--132, 2002.
[15]
Y. Lebbah, C. Michel, and M. Rueher. An efficient and safe framework for solving optimization problems. JCAM (accepted for publication), 2005.
[16]
Y. Lebbah, C. Michel, M. Rueher, D. Daney, and J.-P. Merlet. Efficient and safe global constraints for handling numerical constraint systems. SIAM Journal on Numerical Analysis, 42(5):2076--2097, 2004.
[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]
A. Neumaier and O. Shcherbina. Safe bounds in linear and mixed-integer programming. Mathematical Programming, pages 283--296, 2004.
[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
- Using constraint techniques for a safe and fast implementation of optimality-based reduction
Recommendations
An efficient and safe framework for solving optimization problems
Special issue: Scientific computing, computer arithmetic, and validated numerics (SCAN 2004)Interval methods have shown their ability to locate and prove the existence of a global optima in a safe and rigorous way. Unfortunately, these methods are rather slow. Efficient solvers for optimization problems are based on linear relaxations. However,...
Efficient and Safe Global Constraints for Handling Numerical Constraint Systems
Numerical constraint systems are often handled by branch and prune algorithms that combine splitting techniques, local consistencies, and interval methods. This paper first recalls the principles of {\tt Quad}, a global constraint that works on a tight ...
Optimality-based bound contraction with multiparametric disaggregation for the global optimization of mixed-integer bilinear problems
We address nonconvex mixed-integer bilinear problems where the main challenge is the computation of a tight upper bound for the objective function to be maximized. This can be obtained by using the recently developed concept of multiparametric ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2007
1688 pages
ISBN:1595934804
DOI:10.1145/1244002
- Conference Chairs:
- Yookun Cho,
- Roger L. Wainwright,
- Hisham M. Haddad,
- Sung Y. Shin,
- Program Chair:
- Yong Wan Koo
Copyright © 2007 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 March 2007
Check for updates
Author Tags
Qualifiers
- Article
Conference
SAC07
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,650 of 6,669 submissions, 25%
Upcoming Conference
SAC '25
- Sponsor:
- sigapp
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 100Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 31 Dec 2024
Other Metrics
Citations
Cited By
View all- Puranik YSahinidis N(2017)Domain reduction techniques for global NLP and MINLP optimizationConstraints10.1007/s10601-016-9267-522:3(338-376)Online publication date: 1-Jul-2017
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in