# 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 represented by a node in a directed graph structure.

`EAGO.Node`

— Type`struct Node <: EAGO.AbstractNode`

Describes connectivity and expression represented by node.

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

`EAGO.AtomType`

— Type`AtomType`

`EAGO.AbstractDirectedGraph`

— Type`abstract type AbstractDirectedGraph`

Abstract supertype for generic directed graph structure.

`EAGO.DirectedTree`

— Type`DirectedTree`

A tree graph with a single sink node.

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.

`EAGO.initialize!`

— Method```
initialize!(_::AbstractCache, _::AbstractDirectedGraph)
```

Function used to initialize the storage cache `d::AbstractCache`

for a given type of directed acyclic graph `g::AbstractDirectedGraph`

.

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.

`EAGO.AbstractCacheAttribute`

— Type`abstract type AbstractCacheAttribute`

Abstract supertype used for attributes stored in a cache.

Three included `AbstractCacheAttributes`

are used to

`EAGO.Relax`

— Type`Relax`

Used to dispatch relaxations to a standard

`EAGO.RelaxAA`

— Type`RelaxAA`

`EAGO.RelaxMulEnum`

— Type`RelaxMulEnum`

The forward and reverse routines are overloaded as follows:

`EAGO.f_init!`

— MethodInitializes information in cache `c`

for each node in `g`

that may be used in a forward-pass of attribute `t`

.

`EAGO.fprop!`

— MethodPopulates information associated with attribute `t`

for a variable `v`

at index `k`

in cache `c`

associated with graph `g`

using information at index `k`

.

`EAGO.fprop!`

— MethodPopulates 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`

.

`EAGO.fprop!`

— MethodPopulates 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`

.

`EAGO.fprop!`

— MethodPopulates information associated with attribute `t`

for a parameter `v`

at index `k`

in cache `c`

associated with graph `g`

using information at index `k`

.

`EAGO.fprop!`

— MethodPopulates information associated with attribute `t`

for a constant `v`

at index `k`

in cache `c`

associated with graph `g`

using information at index `k`

.

`EAGO.r_init!`

— MethodInitializes information in cache `c`

for each node in `g`

that may be used in a reverse-pass of attribute `t`

.

`EAGO.rprop!`

— MethodPopulates 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`

.

`EAGO.rprop!`

— MethodPopulates 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`

.

`EAGO.rprop!`

— MethodPopulates 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`

.

`EAGO.rprop!`

— MethodPopulates 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`

.

`EAGO.rprop!`

— MethodPopulates 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`

.

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:

`|b| <= safe b`

,`safe_l <= abs(ai) <= safe u`

, and`safe_l <= abs(ai/aj) <= safe_u`

.