Integrating nonlinear branch-and-bound and outer approximation for convex Mixed Integer Nonlinear Programming

被引：9

作者：

Melo, Wendel ^{[1
]}

Fampa, Marcia ^{[2
,3
]}

Raupp, Fernanda ^{[4
,5
]}

机构：

[1] Univ Fed Rio de Janeiro, Inst Grad Studies & Res Engn COPPE, Rio De Janeiro, Brazil

[2] Univ Fed Rio de Janeiro, Inst Math, Rio De Janeiro, Brazil

[3] Univ Fed Rio de Janeiro, COPPE, BR-21945 Rio De Janeiro, Brazil

[4] Pontificia Univ Catolica Rio de Janeiro, Dept Ind Engn, Rio De Janeiro, Brazil

[5] Natl Lab Sci Comp, Petropolis, Brazil

来源：

JOURNAL OF GLOBAL OPTIMIZATION | 2014年 / 60卷 / 02期

关键词：

Mixed Integer Nonlinear Programming; Branch-and-bound; Outer approximation; Hybrid algorithm; ALGORITHMS; FRAMEWORK;

D O I：

10.1007/s10898-014-0217-8

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we present a new hybrid algorithm for convex Mixed Integer Nonlinear Programming (MINLP). The proposed hybrid algorithm is an improved version of the classical nonlinear branch-and-bound (BB) procedure, where the enhancements are obtained with the application of the outer approximation algorithm on some nodes of the enumeration tree. The two methods are combined in such a way that each one collaborates to the convergence of the other. Computational experiments with benchmark instances of the MINLP problem show the good performance of the proposed algorithm, which is compared to the outer approximation algorithm, the nonlinear BB algorithm and the hybrid algorithm implemented in the solver Bonmin.

引用

页码：373 / 389

页数：17

共 24 条

[1]

Bonami P, 2009, 1664 U WISC MAD COMP

[2]

Bonami P., 2011, More branch-and-bound experiments in convex nonlinear integer programming

[3] An algorithmic framework for convex mixed integer nonlinear programs [J].

Bonami, Pierre ;

Biegler, Lorenz T. ;

Conna, Andrew R. ;

Cornuejols, Gerard ;

Grossmann, Ignacio E. ;

Laird, Carl D. ;

Lee, Jon ;

Lodi, Andrea ;

Margot, Francois ;

Sawaya, Nicolas ;

Wachter, Andreas .

DISCRETE OPTIMIZATION, 2008, 5 (02) :186-204

[4] Heuristics for convex mixed integer nonlinear programs [J].

Bonami, Pierre ;

Goncalves, Joao P. M. .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2012, 51 (02) :729-747

[5] AN IMPROVED BRANCH-AND-BOUND ALGORITHM FOR MIXED-INTEGER NONLINEAR PROGRAMS [J].

BORCHERS, B ;

MITCHELL, JE .

COMPUTERS & OPERATIONS RESEARCH, 1994, 21 (04) :359-367

[6] Nonlinear mixed integer programming for aircraft collision avoidance in free flight [J].

Christodoulou, M ;

Costoulakis, C .

MELECON 2004: PROCEEDINGS OF THE 12TH IEEE MEDITERRANEAN ELECTROTECHNICAL CONFERENCE, VOLS 1-3, 2004, :327-330

[7] AN OUTER-APPROXIMATION ALGORITHM FOR A CLASS OF MIXED-INTEGER NONLINEAR PROGRAMS [J].

DURAN, MA ;

GROSSMANN, IE .

MATHEMATICAL PROGRAMMING, 1986, 36 (03) :307-339

[8]

Geoffrion A. M., 1972, Journal of Optimization Theory and Applications, V10, P237, DOI 10.1007/BF00934810

[9] Generalized convex disjunctive programming: Nonlinear convex hull relaxation [J].

Grossmann, IE ;

Lee, S .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2003, 26 (01) :83-100

[10]

Grossmann IE, 2012, IMA VOL MATH APPL, V154, P93

← 1 2 3 →