struct CNNStructure

Container for the layer structure of a convolutional neural network.

This structure is used for passing the CNN parameters from one function to another. This structure can be created with the get_structure -function.

Fields

• channels: dictionary of (layer, number of channels) pairs for convolutional or pooling layers
• dims: dictionary of (layer, (# of rows, # of columns)) pairs for convolutional or pooling layers
• dense_lengths: dictionary of (layer, # of neurons) pairs for dense and flatten layers
• conv_inds: vector of the convolutional layer indices
• maxpool_inds_inds: vector of the maxpool layer indices
• meanpool_inds: vector of the meanpool layer indices
• flatten_ind: index of the Flux.flatten layer
• dense_inds: vector of the dense layer indices

```

struct TEModel

Universal datatype for storing information about a Tree Ensemble Model. This is the datatype that is used when creating the integer optimization problem from a tree ensemble.

Different tree models (EvoTrees, XGBoost, RandomForest) require individual conversion functions to this datatype.

Fields

• n_trees: number of trees in the ensemble
• n_feats: number of features (input variables) in the model
• n_leaves: number of leaves on each tree
• leaves: indices of the leaves on each tree
• splits: [feature, splitpoint index] pairs accessible by [tree, node]
• splits_ordered: splitpoints ordered by split value for each feature
• n_splits: number of splitpoints for each feature
• predictions: prediction of each node (zero for nodes that are not leaves)
• split_nodes: boolean array containing information whether a node is a split node or not

Splitpoints is the set of unique condition values from the ensemble. Each node is associated with a condition value.

function create_MIP_from_CNN!(jump_model::JuMP.Model, CNN_model::Flux.Chain, cnnstruct::CNNStructure)

Creates a mixed-integer optimization problem from a Flux.Chain convolutional neural network model. The optimization formulation is saved in the JuMP.Model given as an input.

A dummy objective function of 1 is added to the model. The objective is left for the user to define.

The convolutional neural network must follow a certain structure:

• It must consist of (in order) convolutional and pooling layers, a Flux.flatten layer and finally dense layers
• I.e. allowed layer types: Conv, MaxPool, MeanPool, Flux.flatten, Dense
• The activation function for all of the convolutional layers and the dense layers must be ReLU
• The last dense layer must use the identity activation function
• Input size, filter size, stride and padding can be chosen freely

Parameters

• jump_model: an empty optimization model where the formulation will be saved
• CNN_model: Flux.Chain containing the CNN
• cnnstruct: holds the layer structure of the CNN

Optional Parameters

• max_to_mean: formulate maxpool layers as meanpool layers. This might improve the convex hull of the model (linear relaxation) for use with relaxing walk algorithm.
• logging: print progress info to console.

function ICNN_incorporate!(jump::JuMP.Model, filepath::String, output_var, input_vars...)

Incorporates the input convex neural network (ICNN) as an LP into a JuMP model. The model parameters must be contained in a JSON file located in the given filepath. For more information about ICNNs see Amos et al. (2017).

JSON file structure:

• Parameter sets must be named based on the layer type - either "FCx" or "SKIPx" where 'x' indicates the layer number.
• 'FC' indicates a fully connected layer. These parameter sets contain weights and biases.
• 'SKIP' indicates a skip connection layer. These only contain weights.
• For a clear example on how to export these parameters from Tensorflow, see examples/-folder of the package repository

This function modifies the JuMP model given as input. The input and output variable references that are given as input to this function will be linked to the appropriate variables in the ICNN formulation. No additional names are added to the JuMP model - all variables are added as anonymous. Also the JuMP model objective function is modified to include the ICNN output as a penalty term.

Arguments

• jump: JuMP model where the LP formulation should be incorporated
• filepath: relative path to the JSON file containing the model parameters
• output_var: reference to the variable that should be linked to the ICNN output
• input_vars: references to the variables that will be used as the ICNN inputs

function NN_compress(NN_model::Flux.Chain, U_in, L_in, U_bounds, L_bounds)

Compresses a neural network using precomputed bounds.

Arguments

• NN_model: Neural network to be compressed.
• U_in: Upper bounds for the input variables.
• L_in: Lower bounds for the input variables.
• U_bounds: Upper bounds for the other neurons.
• L_bounds: Lower bounds for the other neurons.

Returns a Flux.Chain model of the compressed neural network.

function NN_formulate!(jump_model::JuMP.Model, NN_model::Flux.Chain, U_in, L_in; U_bounds=nothing, L_bounds=nothing, U_out=nothing, L_out=nothing, bound_tightening="fast", compress=false, parallel=false, silent=true)

Creates a mixed-integer optimization problem from a Flux.Chain model.

The parameters are used to specify what kind of bound tightening and compression will be used.

A dummy objective function of 1 is added to the model. The objective is left for the user to define.

Arguments

• jump_model: The constraints and variables will be saved to this optimization model.
• NN_model: Neural network model to be formulated.
• U_in: Upper bounds for the input variables.
• L_in: Lower bounds for the input variables.

Optional arguments

• bound_tightening: Mode selection: "fast", "standard", "output" or "precomputed"
• compress: Should the model be simultaneously compressed?
• parallel: Runs bound tightening in parallel. set_solver!-function must be defined in the global scope, see documentation or examples.
• U_bounds: Upper bounds. Needed if bound_tightening="precomputed"
• L_bounds: Lower bounds. Needed if bound_tightening="precomputed"
• U_out: Upper bounds for the output variables. Needed if bound_tightening="output".
• L_out: Lower bounds for the output variables. Needed if bound_tightening="output".
• silent: Controls console ouput.

function NN_formulate_Psplit!(jump_model::JuMP.Model, NN_model::Flux.Chain, P, U_in, L_in; silent=true)

Creates an optimization problem from a Flux.Chain model using P-split formulation for the disjunctive constraints.

The parameter P specifies the number of splits

A dummy objective function of 1 is added to the model. The objective is left for the user to define.

Arguments

• jump_model: The constraints and variables will be saved to this optimization model.
• NN_model: Neural network model to be formulated.
• P: The number of splits
• U_in: Upper bounds for the input variables.
• L_in: Lower bounds for the input variables.

Optional arguments

• strategy: Controls the partioning strategy. Available options are equalsize (default), equalrange, random, snake
• bound_tightening: How the bounds for neurons are produced. Available options are fast(default), standard, precomputed
• parallel: Is used in standard bounding, for speeding up the formulation default is false
• U_bounds, L_bounds: Upper and lower bounds used in only for precomputed bound-tightening.
• silent: Controls console ouput. Default is true.

function NN_incorporate!(
    jump_original::JuMP.Model,
    param_source,
    output_var,
    input_vars...;
    U_in,
    L_in,
    compress=false,
    bound_tightening="fast",
    parallel=false,
    U_out=nothing,
    L_out=nothing
)

Formulates the neural network (NN) as a MIP into a JuMP model. The model parameters must be contained in a JSON file located at the given filepath OR in a Flux.Chain model.

JSON file structure:

• Parameter sets must be named based on the layer type - "FCx" where 'x' indicates the layer number.
• 'FC' indicates a fully connected layer. These parameter sets contain weights and biases.
• For a clear example on how to export these parameters from Tensorflow, see examples/-folder of the package repository

This function modifies the JuMP model given as input. The input and output variable references that are given as input to this function will be linked to the appropriate variables in the NN formulation. No additional names are added to the JuMP model - all variables are added as anonymous.

Different bound tightening modes and compression can be used. To use bound tightening modes other than "fast", set_solver!-function must be defined in the global scope which defines the solver and other necessary for the JuMP model used in bound tightening.

Arguments

• jump_original: JuMP model into which the neural network MIP should be incorporated
• param_source: relative path to the JSON file containing the model parameters OR a Flux.Chain model
• output_var: reference to the variable that should be linked to the NN output
• input_vars: references to the variables that will be used as the NN inputs

Keyword Arguments

• U_in: vector of upper bounds for the input variables
• L_in: vector of lower bounds for the input variables
• compress: reduce NN size by removing stable and linearly dependent neurons
• bound_tightening: which bound tightening mode to use: "fast", "standard", "output"
• parallel: use multiprocessing for bound tightening
• silent: suppress console output
• U_out: vector of upper bounds for the output variables - necessary when output bound tightening is used
• L_out: vector of lower bounds for the output variables - necessary when output bound tightening is used

Psplits(w::AbstractVector, P::Integer, strategy::String)

Given weight vector w depending on partioning strategy splits indexes of elements of w to P sets. If some of the sets are empty, they are dropped. So, make sure that the number of partitions provided is a meaningful number.

The partions are formed according to the strategy. Possible strategies include "equalsize", "equalrange", "snake" and "random".

Returns P sets of partioned indexes.

function TE_formulate!(opt_model::JuMP.Model, TE::TEModel, objective)

Formulates a tree ensemble to the JuMP model opt_model based on the given tree ensemble TE.

The JuMP model is formulated without the split constraints.

An objective function either minimizing or maximizing the ensemble output is added to the JuMP model.

Arguments

• opt_model: A JuMP model where the formulation will be saved to.
• TE: A tree ensemble model in the universal data type TEModel.
• objective: MINSENSE or MAXSENSE. Minimize or maximize the tree ensemble output.

function add_split_constraints!(opt_model::JuMP.Model, TE::TEModel)

Adds all split constraints to the formulation.

Arguments

• opt_model: A JuMP model containing the formulation.
• TE: A tree ensemble model in the universal data type TEModel.

function anon_NN_from_bounds!(jump::JuMP.Model, W, b, output_var, input_vars...; U_in, L_in, U_bounds, L_bounds)

Helper function for anonymously formulating the NN into a JuMP model given weights, biases and the variable references to be linked.

function build_model!(W, b, K, neurons)

Builds a new Flux.Chain model from the given weights and biases. Modifies the W and b arrays. Helper function of NN_compress.

Returns the new Flux.Chain model.

function calculate_bounds(model::JuMP.Model, layer, neuron, W, b, neurons; layers_removed=0)

Calculates the upper and lower activation bounds for a neuron in a ReLU-activated neural network.

function check_ICNN(optimizer, filepath, output_value, input_values...; show_output=true, negated=false)

Verifies that the output of an ICNN contained in a larger optimization problem formulation is correct. Verification is needed because the ICNN LP formulation cannot detect infeasibility.

Returns true if ICNN output is correct and false otherwise.

Arguments

• optimizer: JuMP optimizer object
• filepath: relative path to the JSON file containing the model parameters
• output_value: ICNN output in the optimal solution of the larger optimization problem
• input_values: the values of the ICNN inputs at the optimal solution of the larger optimization problem

Keyword Arguments

• show_output: print additional information to the console
• negated: set 'true' if the ICNN has been trained with the data negated

function children(id::Int, leaf_dict::Dict, max::Int)

Finds the leaf indices of the children leaves of node id in a binary tree.

Returns an array of the leaf indices.

Arguments

• id: Index of the node in a binary tree. Indexing starts from one and follows level order.
• leaf_dict: A dictionary (map) of the leaf indices accessible by the node indices.
• max: Biggest possible node id in the tree. Used to terminate the search.

function copy_model(input_model, solver_params)

Creates a copy of a JuMP model. Solver has to be specified for each new copy. Used for parallelization.

extract_evotrees_info(evo_model; tree_limit=length(evo_model.trees))

Gets the data required for constructing the corresponding MIP from an EvoTrees model evo_model. Returns a custom datatype TEModel which contains the necessary information.

Arguments

• evo_model: A trained EvoTrees tree ensemble model.

Optional arguments

• tree_limit: only first n trees specified by the argument will be used

function forward_pass!(jump_model::JuMP.Model, input)

Calculates the output of a JuMP model representing a neural network.

function forward_pass_ICNN!(jump, input, output_var, input_vars)

Calculates the forward pass through the ICNN (the output that is produced with the given input).

Arguments

• jump: JuMP model with the ICNN
• input: value to be forward passed
• output_var: reference to the ICNN output variable
• input_vars: references to the ICNN input variables

function forward_pass_NN!(jump, input, output_var, input_vars)

Calculates the forward pass through the NN (the output that is produced with the given input). This function can be used when the NN formulation is incorporated into a larger optimization problem.

Arguments

• jump: JuMP model with the NN formulation
• input: value to be forward passed
• output_var: reference to the NN output variable
• input_vars: references to the NN input variables

function get_Flux_params(NN_model::Flux.Chain)

Helper function for getting the necessary parameters out of a Flux.Chain model. Returns the weights and the biases as vectors.

function get_JSON_params(filepath::String)

Helper function for getting the necessary parameters out of a JSON file. Returns the weights and the biases as vectors.

function get_solution(model::JuMP.Model, TE::TEModel)

Finds the upper and lower bounds for each input variable given the optimized model.

Returns the bounds for each feature in an array.

Arguments

• model: The optimized JuMP model.
• TE: Struct of type TEModel containing information about the tree ensemble.

function get_structure(CNN_model::Flux.Chain, input::Array{Float32, 4})

Extract the layer structure of a convolutional neural network. The input image is needed to calculate the correct sizes for the hidden 2-dimensional layers.

Returns a CNNStructure struct.

function image_pass!(jump_model::JuMP.Model, input::Array{Float32, 4}, cnnstruct::CNNStructure, layer::Int)

Debugging version

Forward pass an image through the JuMP model representing a convolutional neural network.

Returns the output of the layer with index given as input.

function image_pass!(jump_model::JuMP.Model, input::Array{Float32, 4})

Forward pass an image through the JuMP model representing a convolutional neural network.

Returns the output of the network, i.e., a vector of the activations of the last dense layer neurons.

function init_TEModel!(TE::TEModel)

Precompute child leaves which are needed for generating the split constraints. Changes child_leaves field of the TEModel.

function local_search(start, jump_model, U_in, L_in; max_iter=100, epsilon=0.01, show_path=false, silent=true, tolerance=0.001)

Performs relaxing walk local search on the given neural network JuMP formulation. See Tong et al. (2024) for more details.

Parameters

• start: starting point for the search (coordinate in the space)
• jump_model: JuMP model containing the NN formulation
• U_in: upper bounds for the domain
• L_in: lower bounds for the domain

Optional Parameters

• epsilon: controls the step size taken out of the linear region
• show_path: return the path taken by the local search in addition to the optimum
• silent: print progress info to console
• tolerance: minimum relative improvement required at every step to continue the search

function local_search_CNN(start, cnn_jump; epsilon=0.01, max_iter=10, show_path=false, logging=false, tolerance=0.01)

Performs relaxing walk local search on the given convolutional neural network JuMP formulation. See Tong et al. (2024) for more details.

Parameters

• start: starting point for the search (coordinate in the image space)
• cnn_jump: JuMP model containing the CNN formulation

Optional Parameters

• epsilon: controls the step size taken out of the linear region
• max_iter: maximum number of search steps
• show_path: return the path taken by the local search in addition to the optimum
• logging: print progress info to console
• tolerance: minimum relative improvement required at every step to continue the search

function optimize_by_sampling!(jump_model, sample_points; enhanced=true, exploitation_rate=0.67)

Optimizes a neural network by iteratively solving the "local" optimization problem at the sample points. The best (optimum, extremum) solution is returned.

Arguments

• jump_model: JuMP model containing the formulation (and desired objective function)
• sample_points: A matrix where the columns are the sample inputs.

Optional arguments

• enhanced: Controls whether local optimum or only local hyperplane corner is searched for.
• exploitation_rate: Controls how often the algorithm performs local search versus samples a new point.

function optimize_by_walking!(original::JuMP.Model, nn_model::Flux.Chain, U_in, L_in; delta=0.1, return_sampled=false, silent=true, iterations=10, infeasible_per_iter=5)

Performs the full relaxing walk algorithm on the given neural network JuMP formulation. See Tong et al. (2024) for more details.

Parameters

• original: JuMP model containing the NN formulation.
• nn_model: the original NN as Flux.Chain

Optional Parameters

• delta: controls how strongly certain neurons are preferred when fixing the binary variables
• return_sampled: return sampled points in addition to the optima
• silent: print progress info to the console
• iterations: the number of fresh starts from the linear relaxation (no binary variables fixed)
• infeasible_per_iter: the number of infeasible LP relaxations allowed before starting next iteration

function optimize_by_walking_CNN!(cnn_jump::JuMP.Model, input; iterations=10, samples_per_iter=5, timelimit=1.0, tolerance=1.0)

Performs the full relaxing walk algorithm on the given convolutional neural network JuMP formulation. See Tong et al. (2024) for more details.

Parameters

• cnn_jump: JuMP model containing the CNN formulation.
• input: An example input to the CNN. Used to extract the input dimensions.

Optional Parameters

• iterations: the number of fresh starts from the linear relaxation (no binary variables fixed)
• samples_per_iter: maximum number of successful samples per iteration
• timelimit: time limit for the LP relaxation solves
• tolerance: how different new samples must be from any previous one

function prune!(W, b, removed_neurons, layers_removed, neuron_count, layer, bounds_U, bounds_L)

Removes stabily active or inactive neurons in a network by updating the weights and the biases and the removed neurons list accordingly. Helper function of NN_compress.

function tree_callback_algorithm(cb_data, TE::TEModel, opt_model::JuMP.Model)

The callback algorithm for tree ensemble optimization using lazy constraints.

Using lazy constraints, the split constraints are added one-by-one for each tree.

See examples or documentation for information on how to use lazy constraints.

Arguments

• cb_data: Callback data
• TE: A tree ensemble model in the universal data type TEModel.
• opt_model: A JuMP model containing the formulation.