On grid aware refinement of the unit hypercube and simplex: Focus on the complete tree size

L.G. Casado, E.M.T. Hendrix, J.M.G. Salmerón, B.G. Tóth, I. García

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

Abstract

Branch and bound (BnB) Global Optimization algorithms can be used to find the global optimum (minimum) of a multiextremal function over the unit hypercube and unit simplex with a guaranteed accuracy. Subdivision strategies can take the information of the evaluated points into account leading to irregular shaped subsets. This study focuses on the passive generation of spatial subdivisions aiming at evaluating points on a predefined grid. The efficiency measure is in terms of the complete tree size, or worst case BnB scenario, with a termination criterion on the subset size. Longest edge bisection is used as a benchmark. It is shown that taking the grid for a given termination tolerance into account, other general partitions exist that improve the BnB upper bound on the number of evaluated points and subsets.
LanguageEnglish
Title of host publicationComputational Science and Its Applications - ICCSA 2017
Subtitle of host publication17th International Conference, Trieste, Italy, July 3-6, 2017, Proceedings, Part III
EditorsO. Gervasi, B. Murgante, S. Misra, G. Borruso, C.M. Torre, A.M.A.C. Rocha, D. Taniar, B.O. Apduhan, E. Stankova, A. Cuzzocrea
Place of PublicationCham
PublisherSpringer
Pages165-180
ISBN (Electronic)9783319623986
ISBN (Print)9783319623979
DOIs
Publication statusPublished - 2017
EventThe 17th International Conference on Computational Science and Its Applications (ICCSA 2017) - Trieste, Italy
Duration: 3 Jul 20176 Jul 2017

Publication series

NameLecture Notes in Computer Science (LNCS)
Volume10406
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceThe 17th International Conference on Computational Science and Its Applications (ICCSA 2017)
CountryItaly
CityTrieste
Period3/07/176/07/17

Fingerprint

Global optimization

Cite this

Casado, L. G., Hendrix, E. M. T., Salmerón, J. M. G., Tóth, B. G., & García, I. (2017). On grid aware refinement of the unit hypercube and simplex: Focus on the complete tree size. In O. Gervasi, B. Murgante, S. Misra, G. Borruso, C. M. Torre, A. M. A. C. Rocha, D. Taniar, B. O. Apduhan, E. Stankova, ... A. Cuzzocrea (Eds.), Computational Science and Its Applications - ICCSA 2017: 17th International Conference, Trieste, Italy, July 3-6, 2017, Proceedings, Part III (pp. 165-180). (Lecture Notes in Computer Science (LNCS); Vol. 10406). Cham: Springer. https://doi.org/10.1007/978-3-319-62398-6_12
Casado, L.G. ; Hendrix, E.M.T. ; Salmerón, J.M.G. ; Tóth, B.G. ; García, I. / On grid aware refinement of the unit hypercube and simplex: Focus on the complete tree size. Computational Science and Its Applications - ICCSA 2017: 17th International Conference, Trieste, Italy, July 3-6, 2017, Proceedings, Part III. editor / O. Gervasi ; B. Murgante ; S. Misra ; G. Borruso ; C.M. Torre ; A.M.A.C. Rocha ; D. Taniar ; B.O. Apduhan ; E. Stankova ; A. Cuzzocrea. Cham : Springer, 2017. pp. 165-180 (Lecture Notes in Computer Science (LNCS)).
@inbook{dde8a1209b4d4ed5a045878a7ae9eba8,
title = "On grid aware refinement of the unit hypercube and simplex: Focus on the complete tree size",
abstract = "Branch and bound (BnB) Global Optimization algorithms can be used to find the global optimum (minimum) of a multiextremal function over the unit hypercube and unit simplex with a guaranteed accuracy. Subdivision strategies can take the information of the evaluated points into account leading to irregular shaped subsets. This study focuses on the passive generation of spatial subdivisions aiming at evaluating points on a predefined grid. The efficiency measure is in terms of the complete tree size, or worst case BnB scenario, with a termination criterion on the subset size. Longest edge bisection is used as a benchmark. It is shown that taking the grid for a given termination tolerance into account, other general partitions exist that improve the BnB upper bound on the number of evaluated points and subsets.",
author = "L.G. Casado and E.M.T. Hendrix and J.M.G. Salmer{\'o}n and B.G. T{\'o}th and I. Garc{\'i}a",
year = "2017",
doi = "10.1007/978-3-319-62398-6_12",
language = "English",
isbn = "9783319623979",
series = "Lecture Notes in Computer Science (LNCS)",
publisher = "Springer",
pages = "165--180",
editor = "O. Gervasi and B. Murgante and S. Misra and G. Borruso and C.M. Torre and A.M.A.C. Rocha and D. Taniar and B.O. Apduhan and E. Stankova and A. Cuzzocrea",
booktitle = "Computational Science and Its Applications - ICCSA 2017",

}

Casado, LG, Hendrix, EMT, Salmerón, JMG, Tóth, BG & García, I 2017, On grid aware refinement of the unit hypercube and simplex: Focus on the complete tree size. in O Gervasi, B Murgante, S Misra, G Borruso, CM Torre, AMAC Rocha, D Taniar, BO Apduhan, E Stankova & A Cuzzocrea (eds), Computational Science and Its Applications - ICCSA 2017: 17th International Conference, Trieste, Italy, July 3-6, 2017, Proceedings, Part III. Lecture Notes in Computer Science (LNCS), vol. 10406, Springer, Cham, pp. 165-180, The 17th International Conference on Computational Science and Its Applications (ICCSA 2017), Trieste, Italy, 3/07/17. https://doi.org/10.1007/978-3-319-62398-6_12

On grid aware refinement of the unit hypercube and simplex: Focus on the complete tree size. / Casado, L.G.; Hendrix, E.M.T.; Salmerón, J.M.G.; Tóth, B.G.; García, I.

Computational Science and Its Applications - ICCSA 2017: 17th International Conference, Trieste, Italy, July 3-6, 2017, Proceedings, Part III. ed. / O. Gervasi; B. Murgante; S. Misra; G. Borruso; C.M. Torre; A.M.A.C. Rocha; D. Taniar; B.O. Apduhan; E. Stankova; A. Cuzzocrea. Cham : Springer, 2017. p. 165-180 (Lecture Notes in Computer Science (LNCS); Vol. 10406).

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

TY - CHAP

T1 - On grid aware refinement of the unit hypercube and simplex: Focus on the complete tree size

AU - Casado, L.G.

AU - Hendrix, E.M.T.

AU - Salmerón, J.M.G.

AU - Tóth, B.G.

AU - García, I.

PY - 2017

Y1 - 2017

N2 - Branch and bound (BnB) Global Optimization algorithms can be used to find the global optimum (minimum) of a multiextremal function over the unit hypercube and unit simplex with a guaranteed accuracy. Subdivision strategies can take the information of the evaluated points into account leading to irregular shaped subsets. This study focuses on the passive generation of spatial subdivisions aiming at evaluating points on a predefined grid. The efficiency measure is in terms of the complete tree size, or worst case BnB scenario, with a termination criterion on the subset size. Longest edge bisection is used as a benchmark. It is shown that taking the grid for a given termination tolerance into account, other general partitions exist that improve the BnB upper bound on the number of evaluated points and subsets.

AB - Branch and bound (BnB) Global Optimization algorithms can be used to find the global optimum (minimum) of a multiextremal function over the unit hypercube and unit simplex with a guaranteed accuracy. Subdivision strategies can take the information of the evaluated points into account leading to irregular shaped subsets. This study focuses on the passive generation of spatial subdivisions aiming at evaluating points on a predefined grid. The efficiency measure is in terms of the complete tree size, or worst case BnB scenario, with a termination criterion on the subset size. Longest edge bisection is used as a benchmark. It is shown that taking the grid for a given termination tolerance into account, other general partitions exist that improve the BnB upper bound on the number of evaluated points and subsets.

U2 - 10.1007/978-3-319-62398-6_12

DO - 10.1007/978-3-319-62398-6_12

M3 - Chapter

SN - 9783319623979

T3 - Lecture Notes in Computer Science (LNCS)

SP - 165

EP - 180

BT - Computational Science and Its Applications - ICCSA 2017

A2 - Gervasi, O.

A2 - Murgante, B.

A2 - Misra, S.

A2 - Borruso, G.

A2 - Torre, C.M.

A2 - Rocha, A.M.A.C.

A2 - Taniar, D.

A2 - Apduhan, B.O.

A2 - Stankova, E.

A2 - Cuzzocrea, A.

PB - Springer

CY - Cham

ER -

Casado LG, Hendrix EMT, Salmerón JMG, Tóth BG, García I. On grid aware refinement of the unit hypercube and simplex: Focus on the complete tree size. In Gervasi O, Murgante B, Misra S, Borruso G, Torre CM, Rocha AMAC, Taniar D, Apduhan BO, Stankova E, Cuzzocrea A, editors, Computational Science and Its Applications - ICCSA 2017: 17th International Conference, Trieste, Italy, July 3-6, 2017, Proceedings, Part III. Cham: Springer. 2017. p. 165-180. (Lecture Notes in Computer Science (LNCS)). https://doi.org/10.1007/978-3-319-62398-6_12