Edit on GitHub

Nonlinear Backend

Graphs, Caches, Forward and Reverse Propagation

EAGO makes use of a specialized tape structure for each function in order to compute valid composite bounds and relaxations. Each variable, constant, and expression is respresented by a node in a directed graph structure.

EAGO.Node — Type
struct Node <: EAGO.AbstractNode

Describes connectivity and expression represented by node.

source
EAGO.NodeClass — Type
NodeType

Each node in the directed graph can be classified into the following types

  • VARIABLE: Denotes a decision variable.
  • PARAMETER: An adjustable parameter value (not a decision variable).
  • CONSTANT: A constant value
  • EXPRESSION: Any other expression that isn't a subexpression
  • SUBEXPRESSION: Any expression referencing a different graph representation.
source

Each field of the ith EAGO.Node using a basic access function. For instance the ith node's ex_type for graph d may be accessed by ex_type(d, i). The sparsity of node i returns an ordered list of children nodes which form the argument tuple for the operator performed at node i. The sparsity of node i returns a list of parent nodes which form the argument tuple for the operator performed at node i. The parameter_values and constant_values functions are used to access the ith parameter values or ith constant values.

EAGO organizes information associated with each node in a given graph structure using an EAGO.AbstractCache which stores the given information.

EAGO.AbstractCache — Type
abstract type AbstractCache

Abstract supertype used for information storage object the directed acyclic graph.

source
EAGO.initialize! — Method
initialize!(_::AbstractCache, _::AbstractDirectedGraph)

Function used to initialize the storage cache d::AbstractCache for a given type of directed acycle graph g::AbstractDirectedGraph.

source

Information in a given EAGO.AbstractCache is populated by performing a series of forward and reverse passes of the graph structure which dispatch off of an EAGO.AbstractCacheAttribute which indicates what particular information is desired.

Three included AbstractCacheAttributes are used to

The forward and reverse routines are overloaded as follows:

EAGO.f_init! — Method

Initializes information in cache c for each node in g that may be used in a forward-pass of attribute t.

source
EAGO.fprop! — Method

Populates information associated with attribute t for a variable v at index k in cache c associated with graph g using information at index k.

source
EAGO.fprop! — Method

Populates information associated with attribute t for a subexpression v at index k in cache c associated with graph g using information taken from the children of k.

source
EAGO.fprop! — Method

Populates information associated with attribute t for a expression v at index k in cache c associated with graph g using information taken from the children of k.

source
EAGO.fprop! — Method

Populates information associated with attribute t for a parameter v at index k in cache c associated with graph g using information at index k.

source
EAGO.fprop! — Method

Populates information associated with attribute t for a constant v at index k in cache c associated with graph g using information at index k.

source
EAGO.r_init! — Method

Initializes information in cache c for each node in g that may be used in a reverse-pass of attribute t.

source
EAGO.rprop! — Method

Populates information associated with attribute t for a variable v at index k in cache c associated with graph g using information at index k taken from the parents of k.

source
EAGO.rprop! — Method

Populates information associated with attribute t for a subexpressions v at index k in cache c associated with graph g using information at index k taken from the parents of k.

source
EAGO.rprop! — Method

Populates information associated with attribute t for a expressions v at index k in cache c associated with graph g using information at index k taken from the parents of k.

source
EAGO.rprop! — Method

Populates information associated with attribute t for a parameters v at index k in cache c associated with graph g using information at index k taken from the parents of k.

source
EAGO.rprop! — Method

Populates information associated with attribute t for a constant v at index k in cache c associated with graph g using information at index k taken from the parents of k.

source

Forward and reverse subroutines are overloaded for individual operators using through functions of the forms fprop!(t::AbstractCacheAttribute, v::Val{AtomType}, g::AbstractDirectedGraph, b::AbstractCache, k::Int) and rprop!(t::AbstractCacheAttribute, v::Val{AtomType}, g::AbstractDirectedGraph, b::AbstractCache, k::Int).

Other routines

EAGO.is_safe_cut! — Method
is_safe_cut!(m::GlobalOptimizer, f::MathOptInterface.ScalarAffineFunction{Float64}) -> Bool

Applies the safe cut checks detailed in Khajavirad, 2018 [Khajavirad, Aida, and Nikolaos V. Sahinidis. "A hybrid LP/NLP paradigm for global optimization relaxations." Mathematical Programming Computation 10.3 (2018): 383-421] to ensure that only numerically safe affine relaxations are added. Checks that:

  1. |b| <= safe b,
  2. safe_l <= abs(ai) <= safe u, and
  3. safe_l <= abs(ai/aj) <= safe_u.
source