EAGODomainReduction.jl

March 20, 2018 · View on GitHub

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.
  • 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.