### 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.

Language | English |
---|---|

Pages | 305-323 |

Journal | Journal of Global Optimization |

Volume | 64 |

Issue number | 2 |

DOIs | |

Publication status | Published - 2016 |

### Fingerprint

### Keywords

- Branch and bound
- Covering
- Partition
- Unit simplex

### Cite this

*Journal of Global Optimization*,

*64*(2), 305-323. https://doi.org/10.1007/s10898-015-0363-7

}

*Journal of Global Optimization*, vol. 64, no. 2, pp. 305-323. https://doi.org/10.1007/s10898-015-0363-7

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

Research output: Contribution to journal › Article › Academic › peer-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 -