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

摘要

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.