COMBINEMAXCLIQUES Combine the maximal cliques.
[MAXCLIQUES,E] = COMBINEMAXCLIQUES(MAXCLIQUES,E,MAXNUMBEROFCLIQUES,NDISPLAY)
Combine the maximal cliques to reduce computation time. This function
uses the heuristic that an additional variable in a matrix is
equivalent to an additional linking constraint between overlapping
maximal cliques. See [1] for more details.
Inputs:
MAXCLIQUES : Cell array containing the buses contained in each
maximal clique.
E : Matrix with two columns representing the branches of the
maximum weight clique tree formed from the maximal cliques.
Values of E correspond to indices of maxcliques.
MAXNUMBEROFCLIQUES : The maximum number of cliques (stopping
criterion for this combineMaxCliques). If maxNumberOfCliques
is in (0,1), assume maxNumberOfCliques is a fraction of the
original number of maxcliquess. If maxNumberOfCliques is 0, do
not combine maxcliquess (no maximum). If maxNumberOfCliques is
greater than one, cap the number of maxcliques at the specified
value of maxNumberOfCliques.
NDISPLAY : (Optional) Frequency of displaying progress updates.
Outputs:
MAXCLIQUES : Cell array containing the buses contained in each
maximal clique after combining maximal cliques.
E : Matrix with two columns representing the branches of the
maximum weight clique tree formed from the maximal cliques
after combining maximal cliques. Values of E correspond to
indices of maxcliques.
[1] D.K. Molzahn, J.T. Holzer, B.C. Lesieutre, and C.L. DeMarco,
"Implementation of a Large-Scale Optimal Power Flow Solver Based on
Semidefinite Programming," IEEE Transactions on Power Systems,
vol. 28, no. 4, pp. 3987-3998, November 2013.0001 function [maxcliques,E]=combineMaxCliques(maxcliques,E,maxNumberOfCliques,ndisplay) 0002 %COMBINEMAXCLIQUES Combine the maximal cliques. 0003 % [MAXCLIQUES,E] = COMBINEMAXCLIQUES(MAXCLIQUES,E,MAXNUMBEROFCLIQUES,NDISPLAY) 0004 % 0005 % Combine the maximal cliques to reduce computation time. This function 0006 % uses the heuristic that an additional variable in a matrix is 0007 % equivalent to an additional linking constraint between overlapping 0008 % maximal cliques. See [1] for more details. 0009 % 0010 % Inputs: 0011 % MAXCLIQUES : Cell array containing the buses contained in each 0012 % maximal clique. 0013 % E : Matrix with two columns representing the branches of the 0014 % maximum weight clique tree formed from the maximal cliques. 0015 % Values of E correspond to indices of maxcliques. 0016 % MAXNUMBEROFCLIQUES : The maximum number of cliques (stopping 0017 % criterion for this combineMaxCliques). If maxNumberOfCliques 0018 % is in (0,1), assume maxNumberOfCliques is a fraction of the 0019 % original number of maxcliquess. If maxNumberOfCliques is 0, do 0020 % not combine maxcliquess (no maximum). If maxNumberOfCliques is 0021 % greater than one, cap the number of maxcliques at the specified 0022 % value of maxNumberOfCliques. 0023 % NDISPLAY : (Optional) Frequency of displaying progress updates. 0024 % 0025 % Outputs: 0026 % MAXCLIQUES : Cell array containing the buses contained in each 0027 % maximal clique after combining maximal cliques. 0028 % E : Matrix with two columns representing the branches of the 0029 % maximum weight clique tree formed from the maximal cliques 0030 % after combining maximal cliques. Values of E correspond to 0031 % indices of maxcliques. 0032 % 0033 % [1] D.K. Molzahn, J.T. Holzer, B.C. Lesieutre, and C.L. DeMarco, 0034 % "Implementation of a Large-Scale Optimal Power Flow Solver Based on 0035 % Semidefinite Programming," IEEE Transactions on Power Systems, 0036 % vol. 28, no. 4, pp. 3987-3998, November 2013. 0037 0038 % MATPOWER 0039 % Copyright (c) 2013-2016, Power Systems Engineering Research Center (PSERC) 0040 % by Daniel Molzahn, PSERC U of Wisc, Madison 0041 % 0042 % This file is part of MATPOWER. 0043 % Covered by the 3-clause BSD License (see LICENSE file for details). 0044 % See http://www.pserc.cornell.edu/matpower/ for more info. 0045 0046 %% Setup 0047 0048 if nargin < 4 0049 ndisplay = inf; 0050 end 0051 0052 % Intrepret maxNumberOfCliques 0053 if maxNumberOfCliques == 0 0054 maxNumberOfCliques = inf; 0055 elseif maxNumberOfCliques < 1 0056 maxNumberOfCliques = max(round(length(maxcliques)*maxNumberOfCliques),1); 0057 elseif maxNumberOfCliques < 0 0058 error('combineMaxCliques: Invalid maxNumberOfCliques. Must be non-negative.'); 0059 else 0060 % don't change maxNumberOfCliques, the given value is a specified 0061 % number of maxcliques. 0062 end 0063 0064 0065 %% Combine maximal cliques 0066 % Simultaneously update the clique tree. 0067 0068 if length(maxcliques) > maxNumberOfCliques 0069 0070 % Make sure that E has two columns 0071 if size(E,2) < 2 0072 E = E(:).'; 0073 end 0074 E = [E nan(length(E(:,1)),1)]; 0075 0076 % Calculate a cost in terms of number of variables and constraints for 0077 % combining the maximal cliques for each branch of the clique tree. 0078 for i=1:size(E,1) 0079 maxcliquesidx = [E(i,1) E(i,2)]; 0080 E(i,3) = combineCost(maxcliques,maxcliquesidx); 0081 end 0082 0083 while length(maxcliques) > maxNumberOfCliques 0084 0085 % Find the best pair of maximal cliques to combine 0086 [junk,combine_idx] = min(E(:,3)); 0087 maxcliquesidx = [E(combine_idx,1) E(combine_idx,2)]; 0088 0089 % Combine these maximal cliques 0090 maxcliques{E(combine_idx,1)} = unique([maxcliques{E(combine_idx,1)}(:); maxcliques{E(combine_idx,2)}(:)]); 0091 maxcliques = maxcliques(setdiff(1:length(maxcliques),E(combine_idx,2))); 0092 0093 % Update references in E to removed maximal clique 0094 E12 = E(:,1:2); 0095 Eref_removed = find(E12 == E(combine_idx,2)); 0096 E12(Eref_removed) = E(combine_idx,1); 0097 E(:,1:2) = E12; 0098 E = E(setdiff(1:size(E,1),combine_idx),:); 0099 0100 % Any maximal cliques that have indices greater than the removed 0101 % E(combine_idx,2) must have their references corrected. 0102 E12 = E(:,1:2); 0103 Eref_update = find(E12 > maxcliquesidx(2)); 0104 E12(Eref_update) = E12(Eref_update) - 1; 0105 E(:,1:2) = E12; 0106 0107 if maxcliquesidx(2) < maxcliquesidx(1) 0108 maxcliquesidx(1) = maxcliquesidx(1) - 1; 0109 end 0110 0111 % Update E costs 0112 % We need to update the third col of E for any row of E that has a 0113 % reference to the combined maximal cliques 0114 for i=1:size(E,1) 0115 if E(i,1) == maxcliquesidx(1) || E(i,2) == maxcliquesidx(1) 0116 maxcliquesidx_recalc = [E(i,1) E(i,2)]; 0117 E(i,3) = combineCost(maxcliques,maxcliquesidx_recalc); 0118 end 0119 end 0120 0121 if mod(size(E,1),ndisplay) == 0 0122 fprintf('combineLoops: %i maximal cliques of maxNumberOfCliques = %i\n',size(E,1),maxNumberOfCliques); 0123 end 0124 0125 end 0126 else 0127 % No need to combine maximal cliques, the inital set is less than the 0128 % maximum number of maximal cliquess 0129 end