Optimality-based domain reduction for inequality-constrained NLP and MINLP problems

Yi Zhang, Nikolaos V. Sahinidis (), Carlos Nohra and Gang Rong
Additional contact information
Yi Zhang: Zhejiang University
Nikolaos V. Sahinidis: Carnegie Mellon University
Carlos Nohra: Carnegie Mellon University
Gang Rong: Zhejiang University

Journal of Global Optimization, 2020, vol. 77, issue 3, No 1, 425-454

Abstract: Abstract In spatial branch-and-bound algorithms, optimality-based domain reduction is normally performed after solving a node and relies on duality information to reduce ranges of variables. In this work, we propose novel optimality conditions for NLP and MINLP problems and apply them for domain reduction prior to solving a node in branch-and-bound. The conditions apply to nonconvex inequality-constrained problems for which we exploit monotonicity properties of objectives and constraints. We develop three separate reduction algorithms for unconstrained, one-constraint, and multi-constraint problems. We use the optimality conditions to reduce ranges of variables through forward and backward bound propagation of gradients respective to each decision variable. We describe an efficient implementation of these techniques in the branch-and-bound solver BARON. The implementation dynamically recognizes and ignores inactive constraints at each node of the search tree. Our computations demonstrate that the proposed techniques often reduce the solution time and total number of nodes for continuous problems; they are less effective for mixed-integer programs.

Keywords: Branch-and-reduce; Domain reduction; Inequality-constrained problem; Propagation; Mixed-integer nonlinear programming (MINLP); Optimality conditions (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-020-00886-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:77:y:2020:i:3:d:10.1007_s10898-020-00886-z

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-020-00886-z

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().