A polyhedral branch-and-cut approach to global optimization

DOI10.1007/S10107-005-0581-8zbMath1099.90047OpenAlexW2004407575MaRDI QIDQ1780949

Nikolaos V. Sahinidis, Mohit Tawarmalani

Publication date: 14 June 2005

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-005-0581-8

zbMATH Keywords

Outer approximationConvexificationMixed-integer nonlinear programmingConvexity identificationFactorable programming

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Nonconvex programming, global optimization (90C26)

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

COMPARISON BETWEEN FIVE MINLP SOLVERS AND NEW RESULTS RELATED TO TRIGONOMETRIC FUNCTIONS ⋮ EAGO.jl: easy advanced global optimization in Julia ⋮ Optimal design of mixed AC-DC distribution systems for commercial buildings: a nonconvex generalized Benders decomposition approach ⋮ On the numerical solution of the quadratic eigenvalue complementarity problem ⋮ A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming ⋮ Experiments with hybrid Bernstein global optimization algorithm for the OPF problem in power systems ⋮ Multi-fidelity algorithms for the horizontal alignment problem in road design ⋮ An Algorithm for Maximizing a Convex Function Based on Its Minimum ⋮ Strong valid inequalities for orthogonal disjunctions and bilinear covering sets ⋮ Solving generalized polynomial problem by using new affine relaxed technique ⋮ Extended Formulations in Mixed-Integer Convex Programming ⋮ Fast enclosure for the minimum norm least squares solution of the matrix equation AXB = C ⋮ A Deterministic Algorithm for Global Optimization ⋮ Simultaneous Location of Trauma Centers and Helicopters for Emergency Medical Service Planning ⋮ Tractable Relaxations of Composite Functions ⋮ Piecewise polyhedral formulations for a multilinear term ⋮ Mixed-Integer Convex Nonlinear Optimization with Gradient-Boosted Trees Embedded ⋮ Optimizing production capacity and safety stocks in general acyclic supply chains ⋮ Solving binary-constrained mixed complementarity problems using continuous reformulations ⋮ Validation of nominations in gas network optimization: models, methods, and solutions ⋮ Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2 ⋮ Alternative branching rules for some nonconvex problems ⋮ Convex and concave relaxations of implicit functions ⋮ A data-driven matching algorithm for ride pooling problem ⋮ A generic interval branch and bound algorithm for parameter estimation ⋮ A reformulation technique to solve polynomial optimization problems with separable objective functions of bounded integer variables ⋮ A distributionally ambiguous two-stage stochastic approach for investment in renewable generation ⋮ Algorithms for generating Pareto fronts of multi-objective integer and mixed-integer programming problems ⋮ Towards global parameter estimation exploiting reduced data sets ⋮ Models for the two‐dimensional rectangular single large placement problem with guillotine cuts and constrained pattern ⋮ On solving nonsmooth mixed-integer nonlinear programming problems by outer approximation and generalized benders decomposition ⋮ Surrogate-based branch-and-bound algorithms for simulation-based black-box optimization ⋮ Packing convex polygons in minimum-perimeter convex hulls ⋮ Sparse convex optimization toolkit: a mixed-integer framework ⋮ Branch-and-Model: a derivative-free global optimization algorithm ⋮ Strong SOCP Relaxations for the Optimal Power Flow Problem ⋮ Large-Scale Loan Portfolio Selection ⋮ Unnamed Item ⋮ A Recursively Recurrent Neural Network (R2N2) Architecture for Learning Iterative Algorithms ⋮ Equilibrium modeling and solution approaches inspired by nonconvex bilevel programming ⋮ Practical algorithms for multivariate rational approximation ⋮ Proportional packing of circles in a circular container ⋮ Bound-constrained global optimization of functions with low effective dimensionality using multiple random embeddings ⋮ Convex and concave envelopes of artificial neural network activation functions for deterministic global optimization ⋮ An Outer-Inner Approximation for Separable Mixed-Integer Nonlinear Programs ⋮ Complexity guarantees for an implicit smoothing-enabled method for stochastic MPECs ⋮ Improved convex and concave relaxations of composite bilinear forms ⋮ Maximum entropy approach for solving pessimistic bilevel programming problems ⋮ Submodularity in Conic Quadratic Mixed 0–1 Optimization ⋮ Solving Highly Detailed Gas Transport MINLPs: Block Separability and Penalty Alternating Direction Methods ⋮ On the Weber facility location problem with limited distances and side constraints ⋮ Computing the value of the convex envelope of quadratic forms over polytopes through a semidefinite program ⋮ On convex envelopes for bivariate functions over polytopes ⋮ Relaxations of factorable functions with convex-transformable intermediates ⋮ Multi-Tree Decomposition Methods for Large-Scale Mixed Integer Nonlinear Optimization ⋮ 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 ⋮ A general system for heuristic minimization of convex functions over non-convex sets ⋮ Global optimization in stabilizing controller design ⋮ Global solution of non-convex quadratically constrained quadratic programs ⋮ Two-stage stochastic optimization for optimal power flow under renewable generation uncertainty ⋮ Convex quadratic relaxations of nonconvex quadratically constrained quadratic programs ⋮ Global optimization of general non-convex problems with intermediate bilinear substructures ⋮ Primal and dual multi-objective linear programming algorithms for linear multiplicative programmes ⋮ Reachability Analysis and Deterministic Global Optimization of DAE Models ⋮ nlopt ⋮ Global optimization of mathematical programs with complementarity constraints and application to clean energy deployment ⋮ Node selection strategies in interval branch and bound algorithms ⋮ Partially-shared pessimistic bilevel multi-follower programming: concept, algorithm, and application ⋮ A new method for strong-weak linear bilevel programming problem ⋮ Firefly penalty-based algorithm for bound constrained mixed-integer nonlinear programming ⋮ Lower level duality and the global solution of generalized semi-infinite programs ⋮ Solving mixed-integer nonlinear programmes using adaptively refined mixed-integer linear programmes ⋮ Piecewise Linear Function Fitting via Mixed-Integer Linear Programming ⋮ On the Derivation of Continuous Piecewise Linear Approximating Functions ⋮ Tax-Aware Dynamic Asset Allocation ⋮ Global optimization of semi-infinite programs via restriction of the right-hand side ⋮ High-Performance Prototyping of Decomposition Methods in GAMS ⋮ Conflict Analysis for MINLP ⋮ MPEC Methods for Bilevel Optimization Problems ⋮ Minimizing the sum of many rational functions ⋮ Global solutions to a class of CEC benchmark constrained optimization problems ⋮ Normalized multiparametric disaggregation: an efficient relaxation for mixed-integer bilinear problems ⋮ Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods ⋮ A hybrid LP/NLP paradigm for global optimization relaxations ⋮ Trajectory planning for autonomous underwater vehicles in the presence of obstacles and a nonlinear flow field using mixed integer nonlinear programming ⋮ Global optimization with spline constraints: a new branch-and-bound method based on B-splines ⋮ Dynamic coupling of photoacclimation and photoinhibition in a model of microalgae growth ⋮ A review of recent advances in global optimization ⋮ Conic mixed-integer rounding cuts ⋮ Mathematical programming techniques in water network optimization ⋮ A MILP formulation for generalized geometric programming using piecewise-linear approximations ⋮ National-strategic investment in European power transmission capacity ⋮ Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO ⋮ A model for clustering data from heterogeneous dissimilarities ⋮ Floating-point arithmetic on the test bench. How are verified numerical solutions calculated? ⋮ A global MINLP approach to symbolic regression ⋮ Algorithms for unconstrained global optimization of nonlinear (polynomial) programming problems: the single and multi-segment polynomial B-spline approach ⋮ RLT-POS: reformulation-linearization technique-based optimization software for solving polynomial programming problems ⋮ On the product knapsack problem

Uses Software

• BARON
• MINLP

Cites Work

• Unnamed Item
• The convergence rate of the sandwich algorithm for approximating convex functions
• A branch and contract algorithm for problems with concave univariate, bilinear and linear fractional terms
• Convex extensions and envelopes of lower semi-continuous functions
• Approximation of smooth convex bodies by random circumscribed polytopes
• Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, algorithms, software, and applications
• Global optimization of mixed-integer nonlinear programs: a theoretical and computational study
• A branch and cut algorithm for nonconvex quadratically constrained quadratic programming
• A Nonlinear Programming Technique for the Optimization of Continuous Processing Systems
• Convexity and Concavity Detection in Computational Graphs: Tree Walks for Convexity Assessment
• The Cutting-Plane Method for Solving Convex Programs
• An outer-approximation algorithm for a class of mixed-integer nonlinear programs
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• Asymptotic estimates for best and stepwise approximation of convex bodies II
• Discovering the Characteristics of Mathematical Programs via Sampling
• Semidefinite relaxations of fractional programs via novel convexification techniques

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