LaplacianOpt.jl Function References

GraphData

The composite mutable struct, GraphData, holds matrices of adjacency matrix, laplacian matrix, fiedler vector and algebraic connectivity.

LaplacianOptModel

The composite mutable struct, LaplacianOptModel, holds dictionaries for input data, abstract JuMP model for optimization, variable references and result from solving the JuMP model.

LaplacianOptModelOptions

The composite mutable struct, LaplacianOptModelOptions, holds various optimization model options for enhancements with defualt options set to the values provided by get_default_options function.

_PMinorIdx(
    N::Int64,
    sizes::Vector{Int64},
    minors_on_augment_edges::Bool,
    data::Dict{String,Any},
)

Generates a dictionary mapping minor sizes to their corresponding vertex tuples. For each size k in the input sizes vector, creates tuples of k vertices.

_catch_data_input_error(num_nodes::Int64, i::Int64, j::Int64, w_ij::Number)

Given the number of nodes, from and to nodes of an edge, and an edge weight, this function catches any input data error in the JSON file.

_detect_infeasbility_in_data(data::Dict{String, Any})

Given the pre-processed data dictionary, this function detects any infeasibility before building the optimization model.

_is_flow_cut_valid(cutset_f::Vector{Int64}, cutset_t::Vector{Int64}, adjacency::Array{<:Number})

Given from and to sets of vertices of connected components of a graph, this function returns a boolean if the input num_edges number of candidate edge exist to augment or not, between these two sets of vertices.

_violated_eigen_vector(W::Array{<:Number}; tol = 1E-6)

Given a square symmetric matrix, this function returns an eigen vector corresponding to it's most violated eigen value w.r.t positive semi-definiteness of the input matrix.

algebraic_connectivity(adjacency_matrix::Array{<:Number})

Returns the algebraic connectivity or the second smallest eigenvalue of the Laplacian matrix, for an input weighted adjacency matrix of the graph.

cheeger_constant(G::Matrix{<:Number}, 
                 optimizer::MOI.OptimizerWithAttributes; 
                 cheeger_ub = 1E6,
                 optimizer_log = false)

Given a symmetric, weighted adjacency matrix G of a connected graph, and a mixed-integer linear optimizer, this function returns the Cheeger's constant (or isoperimetric number of the graph) and the associated two partitions (S and S_complement) of the graph.

The exact version of the formulation implemented here is published in: Somisetty, N., Nagarajan, H. and Darbha, S., 2024. "Spectral Graph Theoretic Methods for Enhancing Network Robustness in Robot Localization," IEEE 63rd Conference on Decision and Control (CDC), 2024. Link: https://doi.org/10.1109/CDC56724.2024.10886863

References: (I) Chung, F.R., "Laplacians of graphs and Cheeger's inequalities", Combinatorics, Paul Erdos is Eighty, 2(157-172), pp.13-2, 1996. (II) Mohar, B., 1989. Isoperimetric numbers of graphs. Journal of combinatorial theory, Series B, 47(3), pp.274-291. Link: https://doi.org/10.1016/0095-8956(89)90029-4

edge_combinations(n::Int64, k::Int64)

Returns all combinations possible for given n and k.

fiedler_vector(adjacency_matrix::Array{<:Number})

Returns the Fiedler vector or the eigenvector corresponding to the second smallest eigenvalue of the Laplacian matrix for an input weighted adjacency matrix of the graph.

get_data(params::Dict{String, Any})

Given the input params, this function preprocesses the data, catches any error and missing data, and outputs a detailed dictionary which forms the basis for building an optimization model.

get_default_options()

This function returns the default options for building the struct LaplacianOptModelOptions.

get_minor_idx(vector::Vector{Int64}, size::Int64)

Given a vector and the desired size of tuples, this recursive function outputs all possible tuples of the specified size from the elements of the vector.

get_unique_cycles(G::Graphs.SimpleGraphs.SimpleGraph{<:Number}, 
    max_cycle_length::Int, 
    min_cycle_length = 3, 
    ceiling = 100)

Given an undirected graph of type Graphs.SimpleGraphs, this function returns unique cycles of maximum length given by max_cycle_length.

laplacian_matrix(adjacency_matrix::Array{<:Number})

Given a weighted adjacency matrix as an input, this function returns the weighted Laplacian matrix of the graph.

allows the user to set the logging level without the need to add Memento

optimal_graph_edges(adjacency_matrix::Array{<:Number})

Returns a vector of tuples of edges corresponding to an input adjacency matrix of the graph.

optimality_certificate_MISDP(lom::LaplacianOptModel, result::Dict{String,Any})

Given the LaplacianOpt model (lom) and the results dictionary, this function returns a boolean if the integer solution satisfies the optimality certificate for the MISDP problem.

priority_central_nodes(adjacency_augment_graph::Array{<:Number}, num_nodes::Int64)

Returns nodes sorted by their centrality, measured as the sum of edge weights connected to each node, in descending order.

relaxation_bilinear(m::JuMP.Model, xy::JuMP.VariableRef, x::JuMP.VariableRef, y::JuMP.VariableRef)

General relaxation of a binlinear term using McCormick relaxations. This can be used to obtain specific variants in partiuclar cases of variables (when either or both the variables are binary)

z >= JuMP.lower_bound(x)*y + JuMP.lower_bound(y)*x - JuMP.lower_bound(x)*JuMP.lower_bound(y)
z >= JuMP.upper_bound(x)*y + JuMP.upper_bound(y)*x - JuMP.upper_bound(x)*JuMP.upper_bound(y)
z <= JuMP.lower_bound(x)*y + JuMP.upper_bound(y)*x - JuMP.lower_bound(x)*JuMP.upper_bound(y)
z <= JuMP.upper_bound(x)*y + JuMP.lower_bound(y)*x - JuMP.upper_bound(x)*JuMP.lower_bound(y)

round_zeros_ones!(v::Array{<:Number}; tol = 1E-6)

Given a vector of numbers, this function updates the input vector by rounding the values closest to 0, 1 and -1.

Suppresses information and warning messages output by LaplacianOpt, for fine grained control use the Memento package

variable_domain(var::JuMP.VariableRef)

Computes the valid domain of a given JuMP variable taking into account bounds and the varaible's implicit bounds (e.g. binary).

weighted_adjacency_matrix(G::Graphs.SimpleGraphs.SimpleGraph{<:Number}, adjacency_augment_graph::Array{<:Number}, size::Int64)

Returns a weighted adjacency matrix for the connected part of graph.