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-2015 by Power System Engineering Research Center (PSERC) 0040 % by Daniel Molzahn, PSERC U of Wisc, Madison 0041 % 0042 % $Id: combineMaxCliques.m 2644 2015-03-11 19:34:22Z ray $ 0043 % 0044 % This file is part of MATPOWER. 0045 % Covered by the 3-clause BSD License (see LICENSE file for details). 0046 % See http://www.pserc.cornell.edu/matpower/ for more info. 0047 0048 %% Setup 0049 0050 if nargin < 4 0051 ndisplay = inf; 0052 end 0053 0054 % Intrepret maxNumberOfCliques 0055 if maxNumberOfCliques == 0 0056 maxNumberOfCliques = inf; 0057 elseif maxNumberOfCliques < 1 0058 maxNumberOfCliques = max(round(length(maxcliques)*maxNumberOfCliques),1); 0059 elseif maxNumberOfCliques < 0 0060 error('combineMaxCliques: Invalid maxNumberOfCliques. Must be non-negative.'); 0061 else 0062 % don't change maxNumberOfCliques, the given value is a specified 0063 % number of maxcliques. 0064 end 0065 0066 0067 %% Combine maximal cliques 0068 % Simultaneously update the clique tree. 0069 0070 if length(maxcliques) > maxNumberOfCliques 0071 0072 % Make sure that E has two columns 0073 if size(E,2) < 2 0074 E = E(:).'; 0075 end 0076 E = [E nan(length(E(:,1)),1)]; 0077 0078 % Calculate a cost in terms of number of variables and constraints for 0079 % combining the maximal cliques for each branch of the clique tree. 0080 for i=1:size(E,1) 0081 maxcliquesidx = [E(i,1) E(i,2)]; 0082 E(i,3) = combineCost(maxcliques,maxcliquesidx); 0083 end 0084 0085 while length(maxcliques) > maxNumberOfCliques 0086 0087 % Find the best pair of maximal cliques to combine 0088 [junk,combine_idx] = min(E(:,3)); 0089 maxcliquesidx = [E(combine_idx,1) E(combine_idx,2)]; 0090 0091 % Combine these maximal cliques 0092 maxcliques{E(combine_idx,1)} = unique([maxcliques{E(combine_idx,1)}(:); maxcliques{E(combine_idx,2)}(:)]); 0093 maxcliques = maxcliques(setdiff(1:length(maxcliques),E(combine_idx,2))); 0094 0095 % Update references in E to removed maximal clique 0096 E12 = E(:,1:2); 0097 Eref_removed = find(E12 == E(combine_idx,2)); 0098 E12(Eref_removed) = E(combine_idx,1); 0099 E(:,1:2) = E12; 0100 E = E(setdiff(1:size(E,1),combine_idx),:); 0101 0102 % Any maximal cliques that have indices greater than the removed 0103 % E(combine_idx,2) must have their references corrected. 0104 E12 = E(:,1:2); 0105 Eref_update = find(E12 > maxcliquesidx(2)); 0106 E12(Eref_update) = E12(Eref_update) - 1; 0107 E(:,1:2) = E12; 0108 0109 if maxcliquesidx(2) < maxcliquesidx(1) 0110 maxcliquesidx(1) = maxcliquesidx(1) - 1; 0111 end 0112 0113 % Update E costs 0114 % We need to update the third col of E for any row of E that has a 0115 % reference to the combined maximal cliques 0116 for i=1:size(E,1) 0117 if E(i,1) == maxcliquesidx(1) || E(i,2) == maxcliquesidx(1) 0118 maxcliquesidx_recalc = [E(i,1) E(i,2)]; 0119 E(i,3) = combineCost(maxcliques,maxcliquesidx_recalc); 0120 end 0121 end 0122 0123 if mod(size(E,1),ndisplay) == 0 0124 fprintf('combineLoops: %i maximal cliques of maxNumberOfCliques = %i\n',size(E,1),maxNumberOfCliques); 0125 end 0126 0127 end 0128 else 0129 % No need to combine maximal cliques, the inital set is less than the 0130 % maximum number of maximal cliquess 0131 end