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 % $Id: combineMaxCliques.m 2280 2014-01-17 23:28:37Z ray $ 0040 % by Daniel Molzahn, PSERC U of Wisc, Madison 0041 % Copyright (c) 2013-2014 by Power System Engineering Research Center (PSERC) 0042 % 0043 % This file is part of MATPOWER. 0044 % See http://www.pserc.cornell.edu/matpower/ for more info. 0045 % 0046 % MATPOWER is free software: you can redistribute it and/or modify 0047 % it under the terms of the GNU General Public License as published 0048 % by the Free Software Foundation, either version 3 of the License, 0049 % or (at your option) any later version. 0050 % 0051 % MATPOWER is distributed in the hope that it will be useful, 0052 % but WITHOUT ANY WARRANTY; without even the implied warranty of 0053 % MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 0054 % GNU General Public License for more details. 0055 % 0056 % You should have received a copy of the GNU General Public License 0057 % along with MATPOWER. If not, see <http://www.gnu.org/licenses/>. 0058 % 0059 % Additional permission under GNU GPL version 3 section 7 0060 % 0061 % If you modify MATPOWER, or any covered work, to interface with 0062 % other modules (such as MATLAB code and MEX-files) available in a 0063 % MATLAB(R) or comparable environment containing parts covered 0064 % under other licensing terms, the licensors of MATPOWER grant 0065 % you additional permission to convey the resulting work. 0066 0067 %% Setup 0068 0069 if nargin < 4 0070 ndisplay = inf; 0071 end 0072 0073 % Intrepret maxNumberOfCliques 0074 if maxNumberOfCliques == 0 0075 maxNumberOfCliques = inf; 0076 elseif maxNumberOfCliques < 1 0077 maxNumberOfCliques = max(round(length(maxcliques)*maxNumberOfCliques),1); 0078 elseif maxNumberOfCliques < 0 0079 error('combineMaxCliques: Invalid maxNumberOfCliques. Must be non-negative.'); 0080 else 0081 % don't change maxNumberOfCliques, the given value is a specified 0082 % number of maxcliques. 0083 end 0084 0085 0086 %% Combine maximal cliques 0087 % Simultaneously update the clique tree. 0088 0089 if length(maxcliques) > maxNumberOfCliques 0090 0091 % Make sure that E has two columns 0092 if size(E,2) < 2 0093 E = E(:).'; 0094 end 0095 E = [E nan(length(E(:,1)),1)]; 0096 0097 % Calculate a cost in terms of number of variables and constraints for 0098 % combining the maximal cliques for each branch of the clique tree. 0099 for i=1:size(E,1) 0100 maxcliquesidx = [E(i,1) E(i,2)]; 0101 E(i,3) = combineCost(maxcliques,maxcliquesidx); 0102 end 0103 0104 while length(maxcliques) > maxNumberOfCliques 0105 0106 % Find the best pair of maximal cliques to combine 0107 [junk,combine_idx] = min(E(:,3)); 0108 maxcliquesidx = [E(combine_idx,1) E(combine_idx,2)]; 0109 0110 % Combine these maximal cliques 0111 maxcliques{E(combine_idx,1)} = unique([maxcliques{E(combine_idx,1)}(:); maxcliques{E(combine_idx,2)}(:)]); 0112 maxcliques = maxcliques(setdiff(1:length(maxcliques),E(combine_idx,2))); 0113 0114 % Update references in E to removed maximal clique 0115 E12 = E(:,1:2); 0116 Eref_removed = find(E12 == E(combine_idx,2)); 0117 E12(Eref_removed) = E(combine_idx,1); 0118 E(:,1:2) = E12; 0119 E = E(setdiff(1:size(E,1),combine_idx),:); 0120 0121 % Any maximal cliques that have indices greater than the removed 0122 % E(combine_idx,2) must have their references corrected. 0123 E12 = E(:,1:2); 0124 Eref_update = find(E12 > maxcliquesidx(2)); 0125 E12(Eref_update) = E12(Eref_update) - 1; 0126 E(:,1:2) = E12; 0127 0128 if maxcliquesidx(2) < maxcliquesidx(1) 0129 maxcliquesidx(1) = maxcliquesidx(1) - 1; 0130 end 0131 0132 % Update E costs 0133 % We need to update the third col of E for any row of E that has a 0134 % reference to the combined maximal cliques 0135 for i=1:size(E,1) 0136 if E(i,1) == maxcliquesidx(1) || E(i,2) == maxcliquesidx(1) 0137 maxcliquesidx_recalc = [E(i,1) E(i,2)]; 0138 E(i,3) = combineCost(maxcliques,maxcliquesidx_recalc); 0139 end 0140 end 0141 0142 if mod(size(E,1),ndisplay) == 0 0143 fprintf('combineLoops: %i maximal cliques of maxNumberOfCliques = %i\n',size(E,1),maxNumberOfCliques); 0144 end 0145 0146 end 0147 else 0148 % No need to combine maximal cliques, the inital set is less than the 0149 % maximum number of maximal cliquess 0150 end