Investigation of selection strategies in branch and bound algorithm with simplicial partitions and combination of Lipschitz bounds

被引：41

作者：

Paulavicius, Remigijus ^{[1
]}

Zilinskas, Julius ^{[1
]}

Grothey, Andreas ^{[2
]}

机构：

[1] Inst Math & Informat, LT-08663 Vilnius, Lithuania

[2] Univ Edinburgh, Sch Math, Edinburgh EH9 3JZ, Midlothian, Scotland

来源：

OPTIMIZATION LETTERS | 2010年 / 4卷 / 02期

关键词：

Global optimization; Branch and bound; Selection strategies; Lipschitz optimization; Parallel branch and bound; GLOBAL OPTIMIZATION; CONSTANTS;

D O I：

10.1007/s11590-009-0156-3

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Speed and memory requirements of branch and bound algorithms depend on the selection strategy of which candidate node to process next. The goal of this paper is to experimentally investigate this influence to the performance of sequential and parallel branch and bound algorithms. The experiments have been performed solving a number of multidimensional test problems for global optimization. Branch and bound algorithm using simplicial partitions and combination of Lipschitz bounds has been investigated. Similar results may be expected for other branch and bound algorithms.

引用

页码：173 / 183

页数：11

共 21 条

[1]

[Anonymous], APPL OPTIMIZATION

[2]

Baranowska-Bosiacka I, 2005, CELL MOL BIOL LETT, V10, P217

[3]

Ciegis R., 2009, SPRINGER OPTIMIZATIO, V27

[4] Generalized subinterval selection criteria for interval global optimization [J].

Csendes, T .

NUMERICAL ALGORITHMS, 2004, 37 (1-4) :93-100

[5]

DAPUZZO M, 2006, HDB PARALLEL COMPUTI, P225

[6] Probabilistic subproblem selection in branch-and-bound algorithms [J].

Dür, M ;

Stix, V .

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2005, 182 (01) :67-80

[7]

Ferreira A., 1996, LECT NOTES COMPUTER, V1054

[8]

Hansen P., 1995, Handbook of global optimization, P407

[9]

Horst R., 1995, Introduction to Global Optimization

[10]

Jansson C., 1992, GLOBAL MINIMIZATION

← 1 2 3 →