Abstract | ||
---|---|---|
Interval Branch-and-Bound (B&B) algorithms are powerful methods which aim for guaranteed solutions of Global Optimisation problems. Lower bounds for a function in a given interval can be obtained directly with Interval Arithmetic. The use of lower bounds based on Taylor forms show a faster convergence to the minimum with decreasing size of the search interval. Our research focuses on one dimensional functions that can be decomposed into several terms (sub-functions). The question is whether using this characteristic leads to sharper bounds when based on bounds of the sub-functions. This paper deals with functions that are an addition of two sub-functions, also called additively separable functions. The use of the separability is investigated for the so-called Baumann form and Lower Bound Value Form (LBVF). It is proven that using the separability in the LBVF form may lead to a combination of linear minorants that are sharper than the original one. Numerical experiments confirm this improving behaviour and also show that not all separable methods do always provide sharper lower bounds. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/978-3-642-31137-6_9 | ICCSA (3) |
Keywords | Field | DocType |
sharper lower bound,lbvf form,additively separable function,interval branch-and-bound,search interval,additively separable term,sharper bound,separable method,interval arithmetic,lower bound,taylor form | Convergence (routing),Discrete mathematics,Combinatorics,Branch and bound,Mathematical optimization,Upper and lower bounds,Separable space,Interval arithmetic,Mathematics | Conference |
Volume | ISSN | Citations |
7335 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 6 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
José L. Berenguel | 1 | 6 | 1.32 |
Leocadio G. Casado | 2 | 72 | 12.87 |
Inmaculada García | 3 | 55 | 5.61 |
Eligius M. T. Hendrix | 4 | 139 | 26.97 |
F. Messine | 5 | 1 | 0.70 |