Generating a smallest binary tree by proper selection of the longest edges to bisect in a unit simplex refinement

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

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

Abstract

In several areas like global optimization using branch-and-bound methods for mixture design, the unit n-simplex is refined by longest edge bisection (LEB). This process provides a binary search tree. For (Formula presented.), simplices appearing during the refinement process can have more than one longest edge (LE). The size of the resulting binary tree depends on the specific sequence of bisected longest edges. The questions are how to calculate the size of one of the smallest binary trees generated by LEB and how to find the corresponding sequence of LEs to bisect, which can be represented by a set of LE indices. Algorithms answering these questions are presented here. We focus on sets of LE indices that are repeated at a level of the binary tree. A set of LEs was presented in Aparicio et al. (Informatica 26(1):17–32, 2015), for (Formula presented.). An additional question is whether this set is the best one under the so-called (Formula presented.)-valid condition.

LanguageEnglish
Pages389-402
JournalJournal of Combinatorial Optimization
Volume33
Issue number2
DOIs
Publication statusPublished - 2017

Fingerprint

Bisect
Binary trees
Binary Tree
Refinement
Unit
Bisection
Branch and bound method
Mixture Design
Global optimization
Binary Search Tree
Branch and Bound Method
Question Answering
Global Optimization
Optimization Methods
Valid
Calculate

Keywords

  • Bisection sequence
  • Branch-and-bound
  • Combinatorial optimization
  • Longest edge bisection
  • Regular simplex

Cite this

Salmerón, J.M.G. ; Aparicio, G. ; Casado, L.G. ; García, I. ; Hendrix, E.M.T. ; Tóth, B.G. / Generating a smallest binary tree by proper selection of the longest edges to bisect in a unit simplex refinement. In: Journal of Combinatorial Optimization. 2017 ; Vol. 33, No. 2. pp. 389-402.
@article{baf68e5a16ce40539a47079b750cf998,
title = "Generating a smallest binary tree by proper selection of the longest edges to bisect in a unit simplex refinement",
abstract = "In several areas like global optimization using branch-and-bound methods for mixture design, the unit n-simplex is refined by longest edge bisection (LEB). This process provides a binary search tree. For (Formula presented.), simplices appearing during the refinement process can have more than one longest edge (LE). The size of the resulting binary tree depends on the specific sequence of bisected longest edges. The questions are how to calculate the size of one of the smallest binary trees generated by LEB and how to find the corresponding sequence of LEs to bisect, which can be represented by a set of LE indices. Algorithms answering these questions are presented here. We focus on sets of LE indices that are repeated at a level of the binary tree. A set of LEs was presented in Aparicio et al. (Informatica 26(1):17–32, 2015), for (Formula presented.). An additional question is whether this set is the best one under the so-called (Formula presented.)-valid condition.",
keywords = "Bisection sequence, Branch-and-bound, Combinatorial optimization, Longest edge bisection, Regular simplex",
author = "J.M.G. Salmer{\'o}n and G. Aparicio and L.G. Casado and I. Garc{\'i}a and E.M.T. Hendrix and B.G. T{\'o}th",
year = "2017",
doi = "10.1007/s10878-015-9970-y",
language = "English",
volume = "33",
pages = "389--402",
journal = "Journal of Combinatorial Optimization",
issn = "1382-6905",
publisher = "Springer Verlag",
number = "2",

}

Generating a smallest binary tree by proper selection of the longest edges to bisect in a unit simplex refinement. / Salmerón, J.M.G.; Aparicio, G.; Casado, L.G.; García, I.; Hendrix, E.M.T.; Tóth, B.G.

In: Journal of Combinatorial Optimization, Vol. 33, No. 2, 2017, p. 389-402.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Generating a smallest binary tree by proper selection of the longest edges to bisect in a unit simplex refinement

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

AU - Aparicio, G.

AU - Casado, L.G.

AU - García, I.

AU - Hendrix, E.M.T.

AU - Tóth, B.G.

PY - 2017

Y1 - 2017

N2 - In several areas like global optimization using branch-and-bound methods for mixture design, the unit n-simplex is refined by longest edge bisection (LEB). This process provides a binary search tree. For (Formula presented.), simplices appearing during the refinement process can have more than one longest edge (LE). The size of the resulting binary tree depends on the specific sequence of bisected longest edges. The questions are how to calculate the size of one of the smallest binary trees generated by LEB and how to find the corresponding sequence of LEs to bisect, which can be represented by a set of LE indices. Algorithms answering these questions are presented here. We focus on sets of LE indices that are repeated at a level of the binary tree. A set of LEs was presented in Aparicio et al. (Informatica 26(1):17–32, 2015), for (Formula presented.). An additional question is whether this set is the best one under the so-called (Formula presented.)-valid condition.

AB - In several areas like global optimization using branch-and-bound methods for mixture design, the unit n-simplex is refined by longest edge bisection (LEB). This process provides a binary search tree. For (Formula presented.), simplices appearing during the refinement process can have more than one longest edge (LE). The size of the resulting binary tree depends on the specific sequence of bisected longest edges. The questions are how to calculate the size of one of the smallest binary trees generated by LEB and how to find the corresponding sequence of LEs to bisect, which can be represented by a set of LE indices. Algorithms answering these questions are presented here. We focus on sets of LE indices that are repeated at a level of the binary tree. A set of LEs was presented in Aparicio et al. (Informatica 26(1):17–32, 2015), for (Formula presented.). An additional question is whether this set is the best one under the so-called (Formula presented.)-valid condition.

KW - Bisection sequence

KW - Branch-and-bound

KW - Combinatorial optimization

KW - Longest edge bisection

KW - Regular simplex

U2 - 10.1007/s10878-015-9970-y

DO - 10.1007/s10878-015-9970-y

M3 - Article

VL - 33

SP - 389

EP - 402

JO - Journal of Combinatorial Optimization

T2 - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

IS - 2

ER -