Skip to content

MatthewStuber/EAGODomainReduction.jl

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

29 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

EAGODomainReduction.jl

Domain Reduction Procedures in Global Optimization

Build Status Coverage Status codecov.io

Authors

Matthew Wilhelm, Department of Chemical and Biomolecular Engineering, University of Connecticut (UCONN)

Installation

julia> Pkg.add("EAGODomainReduction.jl")

Capabilities

EAGODomainReduction.jl provides a series of subroutines for tightening the domains of subproblems solved in global optimization (potentially to in-feasibility). Currently, it supports routines for nonconvex nonlinear programs:

  • Interval Contractor Propagation: A forward-backward interval contractor using IntervalArthimetic.jl and IntervalContractors.jl for the operator library.
  • Duality-Based Bound Tightening: Provides algorithms for tightening domains based on duality of solutions found for subproblems.
  • Standard Range Reduction: Contracts subproblem domain via linear-relaxations generated using McCormick relaxations.
  • Implicit Subroutine support: Supports domain reduction of reduced space lower-bound problems defined through relaxation of implicit functions by fixed-point methods.

The routine are used extensively in the EAGO.jl package solver. Please see the example files for usage cases.

Future Work

  • Update the interval-constraint propagation algorithm to incorporate propagation heuristics in Vu2008.
  • Incorporate control-flow syntax support into constraint propagation algorithm.
  • Incorporate improvements to probing and optimality based-bound tightening.
  • Add support for Mixed-Integer NLP.

Related Packages

  • EAGO.jl: A package containing global and robust solvers based mainly on McCormick relaxations. This package supports a JuMP and MathProgBase interface.
  • IntervalConstraintProgramming.jl: Provides algorithms that furnish bounds on constraints defined by expressions. The constraint propagation routine in EAGODomainReduction.jl can generate tape objects that are reusable for generically-defined functions. In addition, we use a Vector{Interval} storage object that allows for in-place mutation of intervals.
  • IntervalContractors.jl: Provides a library of reverse interval contractors.

References

  • Benhamou, F., & Older, W.J. (1997). Applying interval arithmetic to real, integer, and boolean constraints. The Journal of Logic Programming, 32, 1–24.
  • Caprara, A., & Locatelli, M. (2010). Global optimization problems and domain reduction strategies. Mathematical Programming, 125, 123–137.
  • Gleixner, A.M., Berthold, T., Müller, B., & Weltge, S. (2016). Three enhancements for optimization-based bound tightening. ZIB Report, 15–16.
  • Ryoo, H.S., & Sahinidis, N.V. (1996). A branch-and-reduce approach to global optimization. Journal of Global Optimization, 8, 107–139.
  • Schichl, H., & Neumaier, A. (2005). Interval analysis on directed acyclic graphs for global optimization. Journal of Global Optimization, 33, 541–562.
  • Tawarmalani, M., & Sahinidis, N.V. (2005). A polyhedral branch-and-cut approach to global optimization. Mathematical Programming, 103, 225–249.
  • Vu, X., Schichl, H., & Sam-Haroud, D. (2009). Interval propagation and search on directed acyclic graphs for numerical constraint solving. Journal of Global Optimization, 45, 499–531.