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.

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

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(num_nodes::Int64, size::Int64)

Given the number of nodes (size of the square matrix) and the preferred size of principal sub-matrices (<= num_nodes), this function outputs all the indices of correspondingly sized sub-matrices.

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 a vector of order of central nodes as an input to construct the graph.

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.