Home > matpower5.0 > extras > sdp_pf > combineMaxCliques.m

combineMaxCliques

PURPOSE ^

COMBINEMAXCLIQUES Combine the maximal cliques.

SYNOPSIS ^

function [maxcliques,E]=combineMaxCliques(maxcliques,E,maxNumberOfCliques,ndisplay)

DESCRIPTION ^

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.

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SOURCE CODE ^

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

Generated on Mon 26-Jan-2015 15:21:31 by m2html © 2005