A branch-and-reduce approach to global optimization

DOI10.1007/BF00138689zbMath0856.90103MaRDI QIDQ1924068

Nikolaos V. Sahinidis, Hong Seo Ryoo

Publication date: 13 October 1996

Published in: Journal of Global Optimization (Search for Journal in Brave)

zbMATH Keywords

global optimizationbranch-and-boundvalid inequalitiesengineering designrange reductionbranch-and-reducepolynomial and multiplicative programsrange contraction techniques

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Mixed integer programming (90C11) Nonlinear programming (90C30) Quadratic programming (90C20)

Related Items (only showing first 100 items - show all)

Deterministic global optimization of binary hybrid distillation/melt-crystallization processes based on relaxed MINLP formulations ⋮ COMPARISON BETWEEN FIVE MINLP SOLVERS AND NEW RESULTS RELATED TO TRIGONOMETRIC FUNCTIONS ⋮ A hybrid LP/NLP paradigm for global optimization relaxations ⋮ Extended reverse-convex programming: an approximate enumeration approach to global optimization ⋮ Theoretical and computational results about optimality-based domain reductions ⋮ Global optimization with spline constraints: a new branch-and-bound method based on B-splines ⋮ Bilinear modeling solution approach for fixed charge network flow problems ⋮ Unnamed Item ⋮ Interval branch-and-bound algorithms for optimization and constraint satisfaction: a survey and prospects ⋮ A FPTAS for a class of linear multiplicative problems ⋮ Reverse logistics network design with stochastic lead times ⋮ Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO ⋮ Solving generalized polynomial problem by using new affine relaxed technique ⋮ An adaptive neighborhood search metaheuristic for the integrated railway rapid transit network design and line planning problem ⋮ RLT-POS: reformulation-linearization technique-based optimization software for solving polynomial programming problems ⋮ Large-scale standard pooling problems with constrained pools and fixed demands ⋮ Bound reduction using pairs of linear inequalities ⋮ Interactions between nonlinear programming and modeling systems ⋮ Mixed integer nonlinear programming tools: an updated practical overview ⋮ Multiplicative programming problems: Analysis and efficient point search heuristic ⋮ GLOMIQO: global mixed-integer quadratic optimizer ⋮ Global optimization of MIQCPs with dynamic piecewise relaxations ⋮ On solving generalized convex MINLP problems using supporting hyperplane techniques ⋮ A Newton method for solving continuous multiple material minimum compliance problems ⋮ Semidefinite relaxations for non-convex quadratic mixed-integer programming ⋮ Strong valid inequalities for Boolean logical pattern generation ⋮ BARON: A general purpose global optimization software package ⋮ Alternative branching rules for some nonconvex problems ⋮ Convex and concave relaxations of implicit functions ⋮ Decomposition strategy for the stochastic pooling problem ⋮ Optimality-based domain reduction for inequality-constrained NLP and MINLP problems ⋮ Global dynamic optimization using edge-concave underestimator ⋮ Deterministic global optimization of process flowsheets in a reduced space using McCormick relaxations ⋮ A reformulation technique to solve polynomial optimization problems with separable objective functions of bounded integer variables ⋮ Surrogate-based branch-and-bound algorithms for simulation-based black-box optimization ⋮ Variable Bound Tightening and Valid Constraints for Multiperiod Blending ⋮ A new bound-and-reduce approach of nonconvex quadratic programming problems ⋮ Convex and concave envelopes of artificial neural network activation functions for deterministic global optimization ⋮ Domain reduction techniques for global NLP and MINLP optimization ⋮ Reduced RLT representations for nonconvex polynomial programming problems ⋮ An efficient strategy for the activation of MIP relaxations in a multicore global MINLP solver ⋮ Global optimization of bounded factorable functions with discontinuities ⋮ On convex relaxations of quadrilinear terms ⋮ Global optimization problems and domain reduction strategies ⋮ Global minimization using an augmented Lagrangian method with variable lower-level constraints ⋮ Deletion Presolve for Accelerating Infeasibility Diagnosis in Optimization Models ⋮ Constraint partitioning in penalty formulations for solving temporal planning problems ⋮ Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON ⋮ SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework ⋮ Bi-perspective functions for mixed-integer fractional programs with indicator variables ⋮ Global optimization in stabilizing controller design ⋮ Bounds tightening based on optimality conditions for nonconvex box-constrained optimization ⋮ Time-optimal velocity planning by a bound-tightening technique ⋮ Three enhancements for optimization-based bound tightening ⋮ Optimality-based bound contraction with multiparametric disaggregation for the global optimization of mixed-integer bilinear problems ⋮ ANTIGONE: algorithms for coNTinuous/Integer global optimization of nonlinear equations ⋮ Multivariate McCormick relaxations ⋮ Global optimization of general nonconvex problems with intermediate polynomial substructures ⋮ On branching-point selection for trilinear monomials in spatial branch-and-bound: the hull relaxation ⋮ Exploiting algebraic structure in global optimization and the Belgian chocolate problem ⋮ Quasiconvex relaxations based on interval arithmetic ⋮ Unnamed Item ⋮ Tighter McCormick relaxations through subgradient propagation ⋮ A joint decomposition method for global optimization of multiscenario nonconvex mixed-integer nonlinear programs ⋮ Global solution of optimization problems with parameter-embedded linear dynamic systems. ⋮ Branch and Win: OR tree search algorithms for solving combinatorial optimisation problems. ⋮ Experimental validation of volume-based comparison for double-McCormick relaxations ⋮ Optimization and analysis of the profitability of tariff structures with two-part tariffs ⋮ Duality for linear multiplicative programs ⋮ Global solution approach for a nonconvex MINLP problem in product portfolio optimization ⋮ Improve-and-branch algorithm for the global optimization of nonconvex NLP problems ⋮ Convergent upper bounds in global minimization with nonlinear equality constraints ⋮ Tuning BARON using derivative-free optimization algorithms ⋮ A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs ⋮ Mixed integer programming for a special logic constrained optimal control problem ⋮ A comparison of complete global optimization solvers ⋮ Design of planar articulated mechanisms using branch and bound ⋮ Global optimization of linear hybrid systems with explicit transitions ⋮ On the Performance of NLP Solvers Within Global MINLP Solvers ⋮ Reachability Analysis and Deterministic Global Optimization of DAE Models ⋮ \(0\text{-}1\) multilinear programming as a unifying theory for LAD pattern generation ⋮ A branch and reduce approach for solving a class of low rank d.c. programs ⋮ Strategic robust supply chain design based on the Pareto-optimal tradeoff between efficiency and risk ⋮ Preface ⋮ Augmented Lagrangians with possible infeasibility and finite termination for global nonlinear programming ⋮ A nonisolated optimal solution of general linear multiplicative programming problems ⋮ A geometric branch and bound method for robust maximization of convex functions ⋮ Branch-and-price for a class of nonconvex mixed-integer nonlinear programs ⋮ Computing the volume of the convex hull of the graph of a trilinear monomial using mixed volumes ⋮ Process planning in a fuzzy environment ⋮ Column enumeration based decomposition techniques for a class of non-convex MINLP problems ⋮ Mixed integer nonlinear programming tools: a practical overview ⋮ On the Composition of Convex Envelopes for Quadrilinear Terms ⋮ Outcome-space cutting-plane algorithm for linear multiplicative programming ⋮ New SOCP relaxation and branching rule for bipartite bilinear programs ⋮ A new class of improved convex underestimators for twice continuously differentiable constrained NLPs ⋮ Accelerating branch-and-bound through a modeling language construct for relaxation-specific constraints ⋮ Optimization-based convex relaxations for nonconvex parametric systems of ordinary differential equations ⋮ A global optimization method, QBB, for twice-differentiable nonconvex optimization problem ⋮ A general purpose exact solution method for mixed integer concave minimization problems

Uses Software

• GAMS
• MINOS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved branch and bound algorithm for minimum concave cost network flow problems
• Convex programs with an additional reverse convex constraint
• Checking local optimality in constrained quadratic programming is NP- hard
• Convergence and restart in branch-and-bound algorithms for global optimization. Application to concave minimization and d.c. optimization problems
• Reverse convex programming
• Effect of the subdivision strategy on convergence and efficiency of some global optimization algorithms
• An analytical approach to global optimization
• An optimality criterion for global quadratic optimization
• A collection of test problems for constrained global optimization algorithms
• A global optimization approach for solving the convex multiplicative programming problem
• Stochastic techniques for global optimization: A survey of recent advances
• A parametric successive underestimation method for convex multiplicative programming problems
• A new reformulation-linearization technique for bilinear programming problems
• Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial
• Calculation of bounds on variables satisfying nonlinear inequality constraints
• A procedure for new product positioning in an attribute space
• Decomposition and interval arithmetic applied to global minimization of polynomial and rational functions
• Optimization methods for computing global minima of nonconvex potential energy functions
• Role of copositivity in optimality criteria for nonconvex optimization problems
• Handbook of global optimization
• The use of Hestenes' method of multipliers to resolve dual gaps in engineering system optimization
• Generalized linear multiplicative and fractional programming
• Polynomial time algorithms for some classes of constrained nonconvex quadratic problems
• Jointly Constrained Biconvex Programming
• Globally minimizing polynomials without evaluating derivatives
• When Is a Point x Satisfying ∇f(x) = 0 a Global Minimum of f?
• An outer-approximation algorithm for a class of mixed-integer nonlinear programs
• A class of exhaustive cone splitting procedures in conical algorithms for concave minmization
• Some NP-complete problems in quadratic and nonlinear programming
• An Algorithm for Global Minimization of Linearly Constrained Concave Quadratic Functions
• Une méthode d'optimisation non linéaire en variables mixtes pour la conception de procédés
• Domain Contraction in Nonlinear Programming: Minimizing a Quadratic Concave Objective Over a Polyhedron
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• An Algorithm for Separable Nonconvex Programming Problems
• On Descent from Local Minima
• An Algorithm for Separable Nonconvex Programming Problems II: Nonconvex Constraints
• Technical Note—Conditions for Global Optimality in Nonlinear Programming
• Global optimization

This page was built for publication: A branch-and-reduce approach to global optimization