Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON. (4th May 2018)

• Record Type: Journal Article
• Authors: Kılınç, Mustafa R.; Sahinidis, Nikolaos V.
• Is Part Of: Optimization methods and software. Volume 33:Number 3(2018)
• Page Start: 540
• Page End: 562
• Publication Date: 2018-05-04
• Subjects: mixed-integer nonlinear programming -- global optimization -- primal heuristics -- portfolios of relaxations; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2017.1350178
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : In this paper, we present recent developments in the global optimization software BARON to address problems with integer variables. A primary development was the addition of mixed-integer linear programming relaxations to BARON's portfolio of linear and nonlinear programming relaxations, aiming to improve dual bounds and offer good starting points for primal heuristics. Since such relaxations necessitate the solution of NP-hard problems, their introduction to a branch-and-bound algorithm raises many practical issues regarding their effective implementation. In addition to describing BARON's dynamic strategy for deciding under what conditions to activate integer programming relaxations in the course of branch-and-bound, the paper also describes cutting plane and probing techniques that originate from the literature of integer linear programming and have been adapted in BARON to solve nonlinear problems. Finally, we describe BARON's primal heuristics for finding good solutions of mixed-integer nonlinear programmes. For all these techniques, we report extensive computational results on a public data set, aiming to analyse the impact of each technique in the solution process and identify techniques that expedite solution the most.