Capabilities of Constraint Programming in Rigorous Global Optimization
Michel Rueher, Alexandre Goldsztejn, Yahia Lebbah, Claude Michel · 2008
Abstract—We investigate the capabilities of constraints programming techniques to boost rigorous global optimiza-tion methods, and thus, to reduce the gap between efficient but unsafe systems like Baron1, and slow but safe global optimization approaches. We show how constraint pro-gramming filtering techniques can be used to implement optimality-based reduction in a safe and efficient way, and thus to take advantage of the known bounds of the objective function to reduce the domain of the variables, and to speed up the search of a global optimum. We describe an efficient strategy to compute very accurate approximations of feasi-ble points. This strategy takes advantage of the Newton method for under-constrained systems of equations and in-equalities to compute efficiently a promising upper bound. Experiments on the COCONUT benchmarks demonstrate that these different techniques drastically improve the per-formances. 1.