Home > matpower5.1 > 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 %   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

Generated on Fri 20-Mar-2015 18:23:34 by m2html © 2005