Affiliations: [1] Research Group TIC146: High Performance Computing – Algorithms, University of Almería, Spain
| [2] Informatics Department, University of Almería (ceiA3), Spain
| [3] Department of Computer Architecture, Universidad de Málaga, Spain
| [4] Department of Differential Equations, Budapest University of Technology and Economics, Hungary. E-mails: [email protected], [email protected], [email protected], [email protected]
Correspondence:
[*]
Corresponding author.
Abstract: In several areas like Global Optimization using branch-and-bound methods, the unit n-simplex is refined by bisecting the longest edge such that a binary search tree appears. This process generates simplices belonging to different shape classes. Having less simplex shapes facilitates the prediction of the further workload from a node in the binary tree, because the same shape leads to the same sub-tree. Irregular sub-simplices generated in the refinement process may have more than one longest edge when n≥3. The question is how to choose the longest edge to be bisected such that the number of shape classes is as small as possible. We develop a Branch-and-Bound (B&B) algorithm to find the minimum number of classes in the refinement process. The developed B&B algorithm provides a minimum number of eight classes for a regular 3-simplex. Due to the high computational cost of solving this combinatorial problem, future research focuses on using high performance computing to derive the minimum number of shapes in higher dimensions.
