Staff Publications

Staff Publications

  • external user (warningwarning)
  • Log in as
  • language uk
  • About

    'Staff publications' is the digital repository of Wageningen University & Research

    'Staff publications' contains references to publications authored by Wageningen University staff from 1976 onward.

    Publications authored by the staff of the Research Institutes are available from 1995 onwards.

    Full text documents are added when available. The database is updated daily and currently holds about 240,000 items, of which 72,000 in open access.

    We have a manual that explains all the features 

Record number 496753
Title On refinement of the unit simplex using regular simplices
Author(s) G.-Tóth, B.; Hendrix, E.M.T.; Casado, L.G.; García, I.
Source Journal of Global Optimization 64 (2016)2. - ISSN 0925-5001 - p. 305 - 323.
DOI http://dx.doi.org/10.1007/s10898-015-0363-7
Department(s) Operations Research and Logistics
WASS
Publication type Refereed Article in a scientific journal
Publication year 2016
Keyword(s) Branch and bound - Covering - Partition - Unit simplex
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.

Comments
There are no comments yet. You can post the first one!
Post a comment
 
Please log in to use this service. Login as Wageningen University & Research user or guest user in upper right hand corner of this page.