Interval Branch-and-Bound algorithms for optimization and constraint satisfaction: a survey and prospects

被引：19

作者：

Araya, Ignacio ^{[1
]}

Reyes, Victor ^{[2
]}

机构：

[1] Pontificia Univ Catolica Valparaiso, Escuela Informat, Ave Brasil 2950, Valparaiso, V Region, Chile

[2] Univ Tecn Federico Santa Maria, Dept Informat, Ave Espana 1680, Valparaiso, V Region, Chile

来源：

JOURNAL OF GLOBAL OPTIMIZATION | 2016年 / 65卷 / 04期

关键词：

Interval arithmetic; Constraint propagation; Numerical constrained optimization; Numerical constraint satisfaction; Interval-based solver; Branch and Bound; DIRECTED ACYCLIC GRAPHS; GLOBAL OPTIMIZATION; LINEAR RELAXATIONS; PROPAGATION; SYSTEMS; EQUATIONS; SELECTION; REGIONS;

D O I：

10.1007/s10898-015-0390-4

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Interval Branch and Bound algorithms are used to solve rigorously continuous constraint satisfaction and constrained global optimization problems. In this paper, we explain the basic principles behind interval Branch and Bound algorithms. We detail the main components and describe issues that should be considered to improve the efficiency of the algorithms.

引用

页码：837 / 866

页数：30

共 125 条

[1]

[Anonymous], 1992, Global optimization using interval analysis

[2]

[Anonymous], 1847, C.R. Acad. Sci. Paris

[3]

[Anonymous], THESIS

[4]

[Anonymous], 2013, PROC ICML

[5]

[Anonymous], 1939, THESIS U CHICAGO CHI

[6]

Araya Ignacio, 2012, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Proceedings 9th International Conference, CPAIOR 2012, P1, DOI 10.1007/978-3-642-29828-8_1

[7]

Araya I., 2010, AAAI

[8]

Araya I, 2008, LECT NOTES COMPUT SC, V5202, P342, DOI 10.1007/978-3-540-85958-1_23

[9] Upper bounding in inner regions for global optimization under inequality constraints [J].

Araya, Ignacio ;

Trombettoni, Gilles ;

Neveu, Bertrand ;

Chabert, Gilles .

JOURNAL OF GLOBAL OPTIMIZATION, 2014, 60 (02) :145-164

[10] More Smear-based Variable Selection Heuristics for NCSPs [J].

Araya, Ignacio ;

Reyes, Victor ;

Orellana, Cristian .

2013 IEEE 25TH INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE (ICTAI), 2013, :1004-1011

← 1 2 3 4 5 6 7 8 9 10 →