Home > matpower7.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 %   Copyright (c) 2013-2019, Power Systems Engineering Research Center (PSERC)
0040 %   by Daniel Molzahn, PSERC U of Wisc, Madison
0041 %
0042 %   This file is part of MATPOWER/mx-sdp_pf.
0043 %   Covered by the 3-clause BSD License (see LICENSE file for details).
0044 %   See https://github.com/MATPOWER/mx-sdp_pf/ 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

Generated on Mon 24-Jun-2019 15:58:45 by m2html © 2005