Tighter McCormick relaxations through subgradient propagation
From MaRDI portal
Publication:2010084
Abstract: Tight convex and concave relaxations are of high importance in the field of deterministic global optimization. We present a heuristic to tighten relaxations obtained by the McCormick technique. We use the McCormick subgradient propagation (Mitsos et al., SIAM J. Optim., 2009) to construct simple affine under- and overestimators of each factor of the original factorable function. Then, we minimize and maximize these affine relaxations in order to obtain possibly improved range bounds for every factor resulting in possibly tighter final McCormick relaxations. We discuss the heuristic and its limitations, in particular the lack of guarantee for improvement. Subsequently, we provide numerical results for benchmark cases found in the COCONUT library and case studies presented in previous works and discuss computational efficiency. We see that the presented heuristic provides a significant improvement in tightness and decrease in computational time in many cases.
Recommendations
Cites work
- scientific article; zbMATH DE number 3649911 (Why is no real title available?)
- scientific article; zbMATH DE number 3898606 (Why is no real title available?)
- scientific article; zbMATH DE number 3936378 (Why is no real title available?)
- scientific article; zbMATH DE number 524102 (Why is no real title available?)
- scientific article; zbMATH DE number 2121575 (Why is no real title available?)
- A branch-and-reduce approach to global optimization
- A finite algorithm for global minimization of separable concave programs
- A note on performance profiles for benchmarking software
- A polyhedral branch-and-cut approach to global optimization
- A reliable affine relaxation method for global optimization
- ANTIGONE: algorithms for coNTinuous/Integer global optimization of nonlinear equations
- Affine arithmetic: concepts and applications
- An analytical approach to global optimization
- Analysis of mathematical programming problems prior to applying the simplex algorithm
- Bounds tightening based on optimality conditions for nonconvex box-constrained optimization
- Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning
- Branching and bounds tighteningtechniques for non-convex MINLP
- Calculation of bounds on variables satisfying nonlinear inequality constraints
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
- Computing the range of values of real functions with accuracy higher than second order
- Convergence analysis of Taylor models and McCormick-Taylor models
- Convergence-order analysis of branch-and-bound algorithms for constrained problems
- Convex optimization algorithms
- Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, algorithms, software, and applications
- Deterministic global optimization of process flowsheets in a reduced space using McCormick relaxations
- Deterministic global optimization with artificial neural networks embedded
- Discretize-then-relax approach for convex/concave relaxations of the solutions of parametric ODEs
- Domain reduction techniques for global NLP and MINLP optimization
- Erratum to: ``Multivariate McCormick relaxations
- Generalized McCormick relaxations
- Global optimization. Theory, algorithms, and applications
- Interval analysis on directed acyclic graphs for global optimization
- McCormick-Based Relaxations of Algorithms
- Multivariate McCormick relaxations
- On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
- On tightness and anchoring of McCormick and other relaxations
- Reverse propagation of McCormick relaxations
- SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework
- The cluster problem in constrained global optimization
- The cluster problem in multivariate global optimization
- The cluster problem revisited
- The global solver in the LINDO API
- Three enhancements for optimization-based bound tightening
- \(\alpha BB\): A global optimization method for general constrained nonconvex problems
Cited in
(13)- Extended McCormick relaxation rules for handling empty arguments representing infeasibility
- A new framework to relax composite functions in nonlinear programs
- Reverse propagation of McCormick relaxations
- Multivariate McCormick relaxations
- Improved convex and concave relaxations of composite bilinear forms
- On tightness and anchoring of McCormick and other relaxations
- Deterministic global optimization with artificial neural networks embedded
- Global dynamic optimization with Hammerstein-Wiener models embedded
- Adjoint mode computation of subgradients for McCormick relaxations
- Optimization-based convex relaxations for nonconvex parametric systems of ordinary differential equations
- Computing subgradients of convex relaxations for solutions of parametric ordinary differential equations
- EAGO.jl: easy advanced global optimization in Julia
- Linearization of McCormick relaxations and hybridization with the auxiliary variable method
Describes a project that uses
Uses Software
This page was built for publication: Tighter McCormick relaxations through subgradient propagation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2010084)
