Implement functions related to clique decomposition

[ivanightingale]

Currently, the implementation of clique decomposition computation and SparseSDPOPF formulation rely on functions from PowerModels.jl. Specifically,

PGLearn.jl/src/opf/opf.jl

Lines 287 to 295 in f07775f

	"""
	_get_clique_decomposition(network::Dict{String,Any})
	Compute the clique decomposition of a PowerModels data dictionary.
	The output is a `Vector{Vector{Int}}` containing all the cliques in the chordal completion of network.
	"""
	function _get_clique_decomposition(network::Dict{String,Any})
	return instantiate_model(network, SparseSDPWRMPowerModel, PM.build_opf).ext[:SDconstraintDecomposition].decomp
	end

PGLearn.jl/src/opf/sparse_sdpwrm.jl

Lines 383 to 412 in f07775f

	"""
	_get_overlapping_pairs(groups)
	Get the indices of pairs of cliques in groups that overlap.
	Refer to https://github.com/lanl-ansi/PowerModels.jl/blob/be6af59202a6868b20a41214cb341b883d62e5f0/src/form/wrm.jl#L273-L274
	"""
	function _get_overlapping_pairs(groups::Vector{Vector{Int}})
	# Compute the clique tree
	tree = PM._prim(PM._overlap_graph(groups))
	# Get the Cartesian indices of the adjacency matrix of the clique tree, which are exactly the indices of pairs
	# of cliques that overlap
	overlapping_pairs = [Tuple(CartesianIndices(tree)[i]) for i in (LinearIndices(tree))[findall(x->x!=0, tree)]]
	return overlapping_pairs
	end
	"""
	idx_a, idx_b = _overlap_indices(A, B)
	Given two arrays (sizes need not match) that share some values, return:
	- linear index of shared values in A
	- linear index of shared values in B
	Thus, A[idx_a] == B[idx_b].
	Refer to https://github.com/lanl-ansi/PowerModels.jl/blob/be6af59202a6868b20a41214cb341b883d62e5f0/src/form/wrm.jl#L469
	"""
	function _overlap_indices(A::Array, B::Array, symmetric=true)
	return PM._overlap_indices(A, B, symmetric)
	end

• Regarding clique decomposition computation, PowerModels.jl computes chordal extension using the Cholesky decomposition (https://github.com/lanl-ansi/PowerModels.jl/blob/be6af59202a6868b20a41214cb341b883d62e5f0/src/form/wrm.jl#L321). This can, for example, be replaced with calls to functions in CliqueTrees.jl, a package specifically for computing chordal extension.
• Regarding SparseSDPOPF formulation: utility functions from PowerModels.jl are being used to compute pairs of cliques with overlapping nodes and indices of identical elements in two arrays. The implementation of these utility functions is not complicated and can probably be taken without making much modification.

[samuelsonric]

@ivanightingale The function chordal_cliques in TSSOS.jl computes a chordal extension of a graph G and returns the maximal cliques. A simpler implementation might look like this.

function chordal_cliques(G; alg=CliqueTrees.MF())
    perm, tree = CliqueTrees.cliquetree(G; alg)
    maximal_cliques = Vector{Vector{Int}}(undef, length(tree))
    
    for (i, clique) in enumerate(tree)
        maximal_cliques[i] = sort!(perm[clique])
    end
    
    return maximal_cliques
end

The input graph G can be have type AbstractGraph or AbstractMatrix. If you do not need each clique to be sorted, you can remove the call to sort!.

[samuelsonric]

See also the function chordal_cliques in PolynomialOptimization.jl.