Domain reduction techniques for global NLP and MINLP optimization
From MaRDI portal
Publication:1699520
DOI10.1007/S10601-016-9267-5zbMATH Open1387.90164arXiv1706.08601OpenAlexW2576928011WikidataQ114859260 ScholiaQ114859260MaRDI QIDQ1699520FDOQ1699520
Authors: Yash Puranik, Nikolaos V. Sahinidis 
Publication date: 23 February 2018
Published in: Constraints (Search for Journal in Brave)
Abstract: Optimization solvers routinely utilize presolve techniques, including model simplification, reformulation and domain reduction techniques. Domain reduction techniques are especially important in speeding up convergence to the global optimum for challenging nonconvex nonlinear programming (NLP) and mixed-integer nonlinear programming (MINLP) optimization problems. In this work, we survey the various techniques used for domain reduction of NLP and MINLP optimization problems. We also present a computational analysis of the impact of these techniques on the performance of various widely available global solvers on a collection of 1740 test problems.
Full work available at URL: https://arxiv.org/abs/1706.08601
Recommendations
- Optimality-based domain reduction for inequality-constrained NLP and MINLP problems
- Reduction constraints for the global optimization of NLPs
- On the Performance of NLP Solvers Within Global MINLP Solvers
- scientific article; zbMATH DE number 1054663
- scientific article; zbMATH DE number 1078157
- Global optimization problems and domain reduction strategies
- scientific article; zbMATH DE number 1054662
- Improve-and-branch algorithm for the global optimization of nonconvex NLP problems
- Theoretical and computational results about optimality-based domain reductions
- A new global optimization method for univariate constrained twice-differentiable NLP problems
domain reductionconstraint propagationfeasibility-based bounds tighteningoptimality-based bounds tightening
Cites Work
- Rigorous global search: continuous problems
- Preprocessing for quadratic programming
- MINLPLib -- a collection of test models for mixed-integer nonlinear programming
- The global solver in the LINDO API
- ICOS: a branch and bound based solver for rigorous global optimization
- SCIP: solving constraint integer programs
- An Automatic Method of Solving Discrete Programming Problems
- Introduction to Interval Analysis
- Solving Mixed Integer Programming Problems Using Automatic Reformulation
- Title not available (Why is that?)
- Convex extensions and envelopes of lower semi-continuous functions
- A polyhedral branch-and-cut approach to global optimization
- Convex envelopes generated from finitely many compact convex sets
- Explicit convex and concave envelopes through polyhedral subdivisions
- Conflict analysis in mixed integer programming
- Mixed integer models for the stationary case of gas network optimization
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Solving Large-Scale Zero-One Linear Programming Problems
- Interval Methods for Systems of Equations
- Mixed integer programming: analyzing 12 years of progress
- An Algorithm for Separable Nonconvex Programming Problems
- Domain filtering consistencies for non-binary constraints
- Title not available (Why is that?)
- Different transformations for solving non-convex trim-loss problems by MINLP
- A polyhedral study of nonconvex quadratic programs with box constraints
- Conflict graphs in solving integer programming problems
- 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
- Heuristics for dynamically adapting propagation in constraint satisfaction problems
- Title not available (Why is that?)
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
- GRASP: a search algorithm for propositional satisfiability
- A new approach to computing optimal schedules for the job-shop scheduling problem
- An analytical approach to global optimization
- Calculation of bounds on variables satisfying nonlinear inequality constraints
- A branch and contract algorithm for problems with concave univariate, bilinear and linear fractional terms
- A convex envelope formula for multilinear functions
- Global optimization of mixed-integer nonlinear programs: a theoretical and computational study
- A branch-and-reduce approach to global optimization
- Global optimization problems and domain reduction strategies
- A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations
- Theoretical and computational results about optimality-based domain reductions
- Complete search in continuous global optimization and constraint satisfaction
- Progress in computational mixed integer programming -- a look back from the other side of the tipping point
- Integrated methods for optimization.
- A reformulation-linearization technique for solving discrete and continuous nonconvex problems
- A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
- Feasibility and infeasibility in optimization. Algorithms and computational methods.
- Molecular Modeling of Proteins and Mathematical Prediction of Protein Structure
- Orbital branching
- Advanced preprocessing techniques for linear and quadratic programming
- Globally solving nonconvex quadratic programming problems via completely positive programming
- Convex envelopes for edge-concave functions
- Accelerating branch-and-bound through a modeling language construct for relaxation-specific constraints
- Branching and bounds tighteningtechniques for non-convex MINLP
- Preprocessing Nonlinear Functional Constraints with Applications to the Pooling Problem
- Analysis of mathematical programming problems prior to applying the simplex algorithm
- Preprocessing and Probing Techniques for Mixed Integer Programming Problems
- Deterministic global optimization using interval constraint propagation techniques
- Global optimization and constraint satisfaction: the branch-and-reduce approach
- Constraint aggregation for rigorous global optimization
- The cluster problem in multivariate global optimization
- A finite algorithm for global minimization of separable concave programs
- Safe bounds in linear and mixed-integer linear programming
- Interval branch-and-bound algorithms for optimization and constraint satisfaction: a survey and prospects
- Mathematical programming techniques in water network optimization
- Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs
- GlobSol user guide
- Convex envelopes of products of convex and component-wise concave functions
- An LPCC approach to nonconvex quadratic programs
- Exclusion Regions for Systems of Equations
- Bound constrained interval global optimization in the COCONUT environment
- Interval analysis on directed acyclic graphs for global optimization
- A branch-and-cut algorithm for nonconvex quadratic programs with box constraints
- A rigorous global filtering algorithm for quadratic constraints
- Bound reduction using pairs of linear inequalities
- Feasibility-based bounds tightening via fixed points
- Learning and propagating Lagrangian variable bounds for mixed-integer nonlinear programming
- Global optimization of general non-convex problems with intermediate bilinear substructures
- The cluster problem revisited
- MINTO, a Mixed INTeger Optimizer
- Seizure warning algorithm based on optimization and nonlinear dynamics
- The essence of constraint propagation
- Applying interval arithmetic to real, integer, and boolean constraints
- The theoretical and empirical rate of convergence for geometric branch-and-bound methods
- Presolving in linear programming
- Title not available (Why is that?)
- Title not available (Why is that?)
- Finding duplicate rows in a linear programming model
- Pruning by isomorphism in branch-and-cut
- Exploiting orbits in symmetric ILP
- Presolve Analysis of Linear Programs Prior to Applying an Interior Point Method
- The Power of Dominance Relations in Branch-and-Bound Algorithms
- Characterization and Theoretical Comparison of Branch-and-Bound Algorithms for Permutation Problems
- Efficient and Safe Global Constraints for Handling Numerical Constraint Systems
- Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis
- A BB\&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times
- Title not available (Why is that?)
- Title not available (Why is that?)
- Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound
- Interval propagation and search on directed acyclic graphs for numerical constraint solving
- Constraint propagation with interval labels
- Exclusion regions for optimization problems
- Redundancy elimination with a lexicographic solved form
- Using dual presolving reductions to reformulate cumulative constraints
- Principles and Practice of Constraint Programming – CP 2004
- Enhancing numerical constraint propagation using multiple inclusion representations
- Global optimization of nonlinear least-squares problems by branch-and-bound and optimality constraints
- Global optimization of nonconvex problems with multilinear intermediates
- Bounds tightening based on optimality conditions for nonconvex box-constrained optimization
- Relaxing the optimality conditions of box QP
- Transposition Theorems and Qualification‐Free Optimality Conditions
- Title not available (Why is that?)
- A probing algorithm for MINLP with failure prediction by SVM
- Three enhancements for optimization-based bound tightening
- Progress in presolving for mixed integer programming
- Logical Reduction Methods in Zero-One Programming—Minimal Preferred Variables
- Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut
- A new dominance procedure for combinatorial optimization problems
- Pruning moves
- Title not available (Why is that?)
- Decompostition of arithmetic expressions to improve the behavior of interval iteration for nonlinear systems
- Title not available (Why is that?)
- Recording and minimizing nogoods from restarts
- Constraint propagation, relational arithmetic in AI systems and mathematical programs
- On Finitely Terminating Branch-and-Bound Algorithms for Some Global Optimization Problems
- Domain Contraction in Nonlinear Programming: Minimizing a Quadratic Concave Objective Over a Polyhedron
- An improved branch and bound algorithm for minimum concave cost network flow problems
- Epsilon-inflation in verification algorithms
- Presolve Reductions in Mixed Integer Programming
- Simple bounds for solutions of monotone complementarity problems and convex programs
- Title not available (Why is that?)
- Computing the range of values of real functions with accuracy higher than second order
- Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning
- Safe and tight linear estimators for global optimization
- Coefficient strengthening: a tool for reformulating mixed-integer programs
- Formal optimization of some reduced linear programming problems
- Linear relaxations and reduced-Cost based propagation of continuous variable subscripts
- Arc-consistency for continuous variables
- A server for automated performance analysis of benchmarking data
- Relaxations of factorable functions with convex-transformable intermediates
- Preprocessing complementarity problems
- The complexity of integer bound propagation
- The AMPL modeling language: an aid to formulating and solving optimization problems
- An Analysis of Slow Convergence in Interval Propagation
- Stronger Inference through Implied Literals from Conflicts and Knapsack Covers
- Deletion presolve for accelerating infeasibility diagnosis in optimization models
- BDD-guided clause generation
Cited In (21)
- Optimal control of water distribution networks without storage
- Variable Bound Tightening and Valid Constraints for Multiperiod Blending
- Tighter McCormick relaxations through subgradient propagation
- Bi-objective design-for-control of water distribution networks with global bounds
- Pyomo.GDP: an ecosystem for logic based modeling and optimization development
- Optimization and validation of pumping system design and operation for water supply in high-rise buildings
- Improved convex and concave relaxations of composite bilinear forms
- Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON
- Global optimality bounds for the placement of control valves in water supply networks
- On the Performance of NLP Solvers Within Global MINLP Solvers
- EAGO.jl: easy advanced global optimization in Julia
- On tackling reverse convex constraints for non-overlapping of unequal circles
- Global optimization problems and domain reduction strategies
- Tuning BARON using derivative-free optimization algorithms
- Optimality-based domain reduction for inequality-constrained NLP and MINLP problems
- Optimal placement of charging station and distributed generation considering electricity price and load uncertainty using NSBSA algorithm
- Title not available (Why is that?)
- Computational advances in polynomial optimization: RAPOSa, a freely available global solver
- Using two-dimensional projections for stronger separation and propagation of bilinear terms
- Global dynamic optimization using edge-concave underestimator
- An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs
Uses Software
This page was built for publication: Domain reduction techniques for global NLP and MINLP optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1699520)
