On refinement of the unit simplex using regular simplices

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

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)

Abstract

A natural way to define branching in branch and bound (B&B) for blending problems is bisection. The consequence of using bisection is that partition sets are in general irregular. The question is how to use regular simplices in the refinement of the unit simplex. A regular simplex with fixed orientation can be represented by its center and size, facilitating storage of the search tree from a computational perspective. The problem is that a simplex defined in a space with dimension (Formula presented.) cannot be subdivided into regular subsimplices without overlapping. We study the characteristics of the refinement by regular simplices. The main challenge is to find a refinement with a good convergence ratio which allows discarding simplices in an overlapped and already evaluated region. As the efficiency of the division rule in B&B algorithms is instance dependent, we focus on the worst case behaviour, i.e. none of the branches are pruned. This paper shows that for this case surprisingly an overlapping regular refinement may generate less simplices to be evaluated than longest edge bisection. On the other hand, the number of evaluated vertices may be larger.

LanguageEnglish
Pages305-323
JournalJournal of Global Optimization
Volume64
Issue number2
DOIs
Publication statusPublished - 2016

Fingerprint

Refinement
Unit
Bisection
Overlapping
Set Partition
Search Trees
Branch-and-bound
Branching
Irregular
Division
Branch
Dependent

Keywords

  • Branch and bound
  • Covering
  • Partition
  • Unit simplex

Cite this

G.-Tóth, B. ; Hendrix, E.M.T. ; Casado, L.G. ; García, I. / On refinement of the unit simplex using regular simplices. In: Journal of Global Optimization. 2016 ; Vol. 64, No. 2. pp. 305-323.
@article{053c73f16d0340d982c24b380bae5bd4,
title = "On refinement of the unit simplex using regular simplices",
abstract = "A natural way to define branching in branch and bound (B&B) for blending problems is bisection. The consequence of using bisection is that partition sets are in general irregular. The question is how to use regular simplices in the refinement of the unit simplex. A regular simplex with fixed orientation can be represented by its center and size, facilitating storage of the search tree from a computational perspective. The problem is that a simplex defined in a space with dimension (Formula presented.) cannot be subdivided into regular subsimplices without overlapping. We study the characteristics of the refinement by regular simplices. The main challenge is to find a refinement with a good convergence ratio which allows discarding simplices in an overlapped and already evaluated region. As the efficiency of the division rule in B&B algorithms is instance dependent, we focus on the worst case behaviour, i.e. none of the branches are pruned. This paper shows that for this case surprisingly an overlapping regular refinement may generate less simplices to be evaluated than longest edge bisection. On the other hand, the number of evaluated vertices may be larger.",
keywords = "Branch and bound, Covering, Partition, Unit simplex",
author = "B. G.-T{\'o}th and E.M.T. Hendrix and L.G. Casado and I. Garc{\'i}a",
year = "2016",
doi = "10.1007/s10898-015-0363-7",
language = "English",
volume = "64",
pages = "305--323",
journal = "Journal of Global Optimization",
issn = "0925-5001",
publisher = "Springer Verlag",
number = "2",

}

On refinement of the unit simplex using regular simplices. / G.-Tóth, B.; Hendrix, E.M.T.; Casado, L.G.; García, I.

In: Journal of Global Optimization, Vol. 64, No. 2, 2016, p. 305-323.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - On refinement of the unit simplex using regular simplices

AU - G.-Tóth, B.

AU - Hendrix, E.M.T.

AU - Casado, L.G.

AU - García, I.

PY - 2016

Y1 - 2016

N2 - A natural way to define branching in branch and bound (B&B) for blending problems is bisection. The consequence of using bisection is that partition sets are in general irregular. The question is how to use regular simplices in the refinement of the unit simplex. A regular simplex with fixed orientation can be represented by its center and size, facilitating storage of the search tree from a computational perspective. The problem is that a simplex defined in a space with dimension (Formula presented.) cannot be subdivided into regular subsimplices without overlapping. We study the characteristics of the refinement by regular simplices. The main challenge is to find a refinement with a good convergence ratio which allows discarding simplices in an overlapped and already evaluated region. As the efficiency of the division rule in B&B algorithms is instance dependent, we focus on the worst case behaviour, i.e. none of the branches are pruned. This paper shows that for this case surprisingly an overlapping regular refinement may generate less simplices to be evaluated than longest edge bisection. On the other hand, the number of evaluated vertices may be larger.

AB - A natural way to define branching in branch and bound (B&B) for blending problems is bisection. The consequence of using bisection is that partition sets are in general irregular. The question is how to use regular simplices in the refinement of the unit simplex. A regular simplex with fixed orientation can be represented by its center and size, facilitating storage of the search tree from a computational perspective. The problem is that a simplex defined in a space with dimension (Formula presented.) cannot be subdivided into regular subsimplices without overlapping. We study the characteristics of the refinement by regular simplices. The main challenge is to find a refinement with a good convergence ratio which allows discarding simplices in an overlapped and already evaluated region. As the efficiency of the division rule in B&B algorithms is instance dependent, we focus on the worst case behaviour, i.e. none of the branches are pruned. This paper shows that for this case surprisingly an overlapping regular refinement may generate less simplices to be evaluated than longest edge bisection. On the other hand, the number of evaluated vertices may be larger.

KW - Branch and bound

KW - Covering

KW - Partition

KW - Unit simplex

U2 - 10.1007/s10898-015-0363-7

DO - 10.1007/s10898-015-0363-7

M3 - Article

VL - 64

SP - 305

EP - 323

JO - Journal of Global Optimization

T2 - Journal of Global Optimization

JF - Journal of Global Optimization

SN - 0925-5001

IS - 2

ER -