Informatica Logo

INFORMATICA
International Journal

Main Page
Editorial Board
Abstracting/Indexing
Instructions to Authors
Subscription Information


Contents
Author Index
Papers in Production

INFORMATICA, 2016, Vol. 27, No. 2, 351-366
© Institute of Mathematics and Informatics,
DOI: http://dx.doi.org/10.15388/Informatica.2016.89

ISSN 0868-4952

On Bisecting the Unit Simplex Using Various Distance Norms

Jose M.G. SALMERÓN1, Leocadio G. CASADO, Eligius M.T. HENDRIX

Informatics Department, University of Almería (ceiA3), Spain Department of Computer Architecture, Universidad de Málaga, Spain E-mail: josemanuel@ual.es, leo@ual.es, eligius@uma.es

Abstract

The iterative bisection of the longest edge of the unit simplex generates a binary tree, where the specific shape depends on the chosen longest edges to be bisected. In global optimization, the use of various distance norms may be advantageous for bounding purposes. The question dealt with in this paper is how the size of a binary tree generated by the refinement process depends on heuristics for longest edge selection when various distance norms are used. We focus on the minimum size of the tree that can be reached, how selection criteria may reduce the size of the tree compared to selecting the first edge, whether a predefined grid is covered and how unique are the selection criteria. The exact numerical values are provided for the unit simplex in 4 and 5-dimensional space.

Keywords:

simplex, Branch-and-Bound, longest edge bisection, norm, selection heuristics


1Corresponding author.
To preview Lithuanian abstract see full article text

PDFTo preview full article text in PDF format click here

Get Free ReaderYou could obtain free Acrobat Reader from Adobe


TopTop Copyright © INFORMATICA, Vilnius University Institute of Mathematics and Informatics, 2010