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 () and B. G.-Tóth ()
Additional contact information
J. M. G. Salmerón: University of Almería (ceiA3)
G. Aparicio: University of Almería (ceiA3)
L. G. Casado: University of Almería (ceiA3)
I. García: Universidad de Málaga
E. M. T. Hendrix: Universidad de Málaga
B. G.-Tóth: Budapest University of Technology and Economics

Journal of Combinatorial Optimization, 2017, vol. 33, issue 2, No 3, 389-402

Abstract: 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 $$n>2$$ n > 2 , 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 $$n=3$$ n = 3 . An additional question is whether this set is the best one under the so-called $$m_k$$ m k -valid condition.

Keywords: Regular simplex; Longest edge bisection; Branch-and-bound; Bisection sequence; Combinatorial optimization (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9970-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:33:y:2017:i:2:d:10.1007_s10878-015-9970-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9970-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().