ConnectivityBreakAnalysis.java
/**
* Copyright (c) 2020, RTE (http://www.rte-france.com)
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
* SPDX-License-Identifier: MPL-2.0
*/
package com.powsybl.openloadflow.dc.fastdc;
import com.powsybl.contingency.BranchContingency;
import com.powsybl.math.matrix.DenseMatrix;
import com.powsybl.openloadflow.dc.DcLoadFlowContext;
import com.powsybl.openloadflow.dc.equations.ClosedBranchSide1DcFlowEquationTerm;
import com.powsybl.openloadflow.dc.equations.DcEquationType;
import com.powsybl.openloadflow.dc.equations.DcVariableType;
import com.powsybl.openloadflow.equations.EquationSystem;
import com.powsybl.openloadflow.graph.GraphConnectivity;
import com.powsybl.openloadflow.network.*;
import com.powsybl.openloadflow.network.action.AbstractLfBranchAction;
import com.powsybl.openloadflow.network.action.LfAction;
import com.powsybl.openloadflow.network.impl.PropagatedContingency;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;
/**
* @author Geoffroy Jamgotchian {@literal <geoffroy.jamgotchian at rte-france.com>}
* @author Ga��l Macherel {@literal <gael.macherel@artelys.com>}
*/
public final class ConnectivityBreakAnalysis {
private static final double CONNECTIVITY_LOSS_THRESHOLD = 10e-7;
private static final Logger LOGGER = LoggerFactory.getLogger(ConnectivityBreakAnalysis.class);
public record DisabledElements(Set<LfBus> disabledBuses, Set<LfBranch> partialDisabledBranches, Set<LfHvdc> hvdcsWithoutPower) {
public static final DisabledElements NO_DISABLED_ELEMENTS = new DisabledElements(Collections.emptySet(), Collections.emptySet(), Collections.emptySet());
}
public static final class ConnectivityAnalysisResult {
private final PropagatedContingency propagatedContingency;
private final LfNetwork network;
private final Set<String> elementsToReconnect;
private final Set<LfBus> slackConnectedComponent; // buses of connected component where the slack is
private final int createdSynchronousComponents;
private final DisabledElements disabledElements;
private final List<LfAction> lfActions;
public ConnectivityAnalysisResult(PropagatedContingency nonBreakingConnectivityContingency, LfNetwork network) {
this(nonBreakingConnectivityContingency, Collections.emptyList(), network);
}
public ConnectivityAnalysisResult(PropagatedContingency nonBreakingConnectivityContingency, List<LfAction> lfActions, LfNetwork network) {
this(nonBreakingConnectivityContingency, network, Collections.emptySet(), DisabledElements.NO_DISABLED_ELEMENTS, Collections.emptySet(), 0, lfActions);
}
public ConnectivityAnalysisResult(PropagatedContingency propagatedContingency, LfNetwork network, Set<String> elementsToReconnect,
DisabledElements disabledElements, Set<LfBus> slackConnectedComponentBuses,
int createdSynchronousComponents, List<LfAction> lfActions) {
this.propagatedContingency = Objects.requireNonNull(propagatedContingency);
this.network = Objects.requireNonNull(network);
this.elementsToReconnect = elementsToReconnect;
this.disabledElements = disabledElements;
this.slackConnectedComponent = slackConnectedComponentBuses;
this.createdSynchronousComponents = createdSynchronousComponents;
this.lfActions = lfActions;
}
public PropagatedContingency getPropagatedContingency() {
return propagatedContingency;
}
public Set<String> getElementsToReconnect() {
return elementsToReconnect;
}
public Set<LfBus> getDisabledBuses() {
return disabledElements.disabledBuses;
}
public Set<LfBus> getSlackConnectedComponent() {
return slackConnectedComponent;
}
public Set<LfBranch> getPartialDisabledBranches() {
return disabledElements.partialDisabledBranches;
}
public Set<LfHvdc> getHvdcsWithoutPower() {
return disabledElements.hvdcsWithoutPower;
}
public List<LfAction> getLfActions() {
return lfActions;
}
public Optional<LfContingency> toLfContingency() {
PropagatedContingency.ContingencyConnectivityLossImpactAnalysis analysis = (network, contingencyId, branchesToOpen, relocateSlackBus)
-> new PropagatedContingency.ContingencyConnectivityLossImpact(createdSynchronousComponents, disabledElements.disabledBuses, disabledElements.hvdcsWithoutPower);
return propagatedContingency.toLfContingency(network, false, analysis);
}
public ConnectivityAnalysisResult withLfActions(List<LfAction> lfActions) {
return new ConnectivityAnalysisResult(this.propagatedContingency, this.network, this.elementsToReconnect, this.disabledElements,
this.slackConnectedComponent, this.createdSynchronousComponents, lfActions
);
}
}
public record ConnectivityBreakAnalysisResults(List<PropagatedContingency> nonBreakingConnectivityContingencies,
List<ConnectivityAnalysisResult> connectivityAnalysisResults,
DenseMatrix contingenciesStates,
Map<String, ComputedContingencyElement> contingencyElementByBranch) {
}
private ConnectivityBreakAnalysis() {
}
private record States(DenseMatrix contingencyStates, DenseMatrix actionStates) {
}
private static void detectPotentialConnectivityBreak(LfNetwork lfNetwork, DenseMatrix contingencyStates, List<PropagatedContingency> contingencies,
Map<String, ComputedContingencyElement> contingencyElementByBranch,
EquationSystem<DcVariableType, DcEquationType> equationSystem,
List<PropagatedContingency> nonBreakingConnectivityContingencies,
List<PropagatedContingency> potentiallyBreakingConnectivityContingencies) {
for (PropagatedContingency contingency : contingencies) {
if (isConnectivityPotentiallyModifiedByContingencyAndOperatorStrategy(lfNetwork, new States(contingencyStates, DenseMatrix.EMPTY), contingency, contingencyElementByBranch,
Collections.emptyList(), Collections.emptyMap(), equationSystem)) { // connectivity broken
potentiallyBreakingConnectivityContingencies.add(contingency);
} else {
nonBreakingConnectivityContingencies.add(contingency);
}
}
}
/**
* Returns true if the given contingency and operator strategy actions potentially break connectivity.
* This is determined with a "worst case" sensitivity-criterion. If the criterion is not verified, there is no connectivity break.
*/
private static boolean isConnectivityPotentiallyModifiedByContingencyAndOperatorStrategy(LfNetwork lfNetwork, States states, PropagatedContingency contingency,
Map<String, ComputedContingencyElement> contingencyElementByBranch, List<LfAction> operatorStrategyLfActions,
Map<LfAction, AbstractComputedElement> actionElementByBranch, EquationSystem<DcVariableType, DcEquationType> equationSystem) {
List<ComputedContingencyElement> contingencyElements = contingency.getBranchIdsToOpen().keySet().stream()
.map(contingencyElementByBranch::get)
.collect(Collectors.toList());
// The sensitivity criterion only considers actions that disable branches in order to compute a "worst-case" scenario,
// i.e. that if the criterion is not met, there is no connectivity break.
// As the actions removed either have no impact or can only close branches (and therefore affect the criterion negatively),
// it is not necessary to consider them to ensure that there is no loss of connectivity.
List<AbstractComputedElement> actionElements = operatorStrategyLfActions.stream()
.map(actionElementByBranch::get)
.filter(actionElement -> actionElement instanceof ComputedSwitchBranchElement computedSwitchBranchElement && !computedSwitchBranchElement.isEnabled())
.collect(Collectors.toList());
return isGroupOfElementsBreakingConnectivity(lfNetwork, states.contingencyStates(), contingencyElements, states.actionStates(), actionElements, equationSystem);
}
private static boolean isGroupOfElementsBreakingConnectivity(LfNetwork lfNetwork, DenseMatrix contingenciesStates,
List<ComputedContingencyElement> contingencyElements,
DenseMatrix actionStates, List<AbstractComputedElement> actionElements,
EquationSystem<DcVariableType, DcEquationType> equationSystem) {
// use a sensitivity-criterion to detect the loss of connectivity after a contingency
// we consider a +1 -1 on a line, and we observe the sensitivity of these injections on the other contingency elements
// if the sum of the sensitivities (in absolute value) is 1, it means that all the flow is going through the lines with a non-zero sensitivity
// thus, losing these lines will lose the connectivity
List<AbstractComputedElement> computedElements = Stream.concat(contingencyElements.stream(), actionElements.stream()).toList();
for (AbstractComputedElement element : computedElements) {
double sum = 0d;
for (AbstractComputedElement element2 : computedElements) {
LfBranch branch = lfNetwork.getBranchById(element2.getLfBranch().getId());
ClosedBranchSide1DcFlowEquationTerm p = equationSystem.getEquationTerm(ElementType.BRANCH, branch.getNum(), ClosedBranchSide1DcFlowEquationTerm.class);
DenseMatrix elementMatrix = element2 instanceof ComputedContingencyElement ? contingenciesStates : actionStates;
double value = Math.abs(p.calculateSensi(elementMatrix, element.getComputedElementIndex()));
sum += value;
}
if (sum > 1d - CONNECTIVITY_LOSS_THRESHOLD) {
// all lines that have a non-0 sensitivity associated to "element" breaks the connectivity
return true;
}
}
return false;
}
private static List<ConnectivityAnalysisResult> computeConnectivityData(LfNetwork lfNetwork, List<PropagatedContingency> potentiallyBreakingConnectivityContingencies,
Map<String, ComputedContingencyElement> contingencyElementByBranch,
List<PropagatedContingency> nonBreakingConnectivityContingencies) {
if (potentiallyBreakingConnectivityContingencies.isEmpty()) {
return Collections.emptyList();
}
List<ConnectivityAnalysisResult> connectivityAnalysisResults = new ArrayList<>();
for (PropagatedContingency propagatedContingency : potentiallyBreakingConnectivityContingencies) {
// compute connectivity analysis result, with contingency only
ConnectivityAnalysisResult connectivityAnalysisResult = computeConnectivityAnalysisResult(lfNetwork, propagatedContingency, contingencyElementByBranch, Collections.emptyList(), Collections.emptyMap());
if (connectivityAnalysisResult != null) {
connectivityAnalysisResults.add(connectivityAnalysisResult);
} else {
// no connectivity break
nonBreakingConnectivityContingencies.add(propagatedContingency);
}
}
return connectivityAnalysisResults;
}
/**
* Compute post contingency and operator strategy connectivity analysis result by analyzing network connectivity.
* Both contingency and actions can impact connectivity.
*/
private static ConnectivityAnalysisResult computeConnectivityAnalysisResult(LfNetwork lfNetwork,
PropagatedContingency contingency, Map<String, ComputedContingencyElement> contingencyElementByBranch,
List<LfAction> lfActions, Map<LfAction, AbstractComputedElement> actionElementByBranch) {
GraphConnectivity<LfBus, LfBranch> connectivity = lfNetwork.getConnectivity();
// concatenate all computed elements, to apply them on the connectivity
List<AbstractComputedElement> modifyingConnectivityCandidates = Stream.concat(
contingency.getBranchIdsToOpen().keySet().stream().map(contingencyElementByBranch::get),
lfActions.stream().map(actionElementByBranch::get)
).sorted(Comparator.comparing(element -> element.getLfBranch().getId())).toList();
// we confirm the breaking of connectivity by network connectivity
ConnectivityAnalysisResult connectivityAnalysisResult = null;
connectivity.startTemporaryChanges();
try {
// apply all modifications of connectivity, due to the lost/enabled/disabled branches
modifyingConnectivityCandidates.forEach(computedElement -> computedElement.applyToConnectivity(connectivity));
// filter the branches that really impacts connectivity
// the traversal order of the set must be deterministic to ensure consistent element selection when multiple elements can restore connectivity
// without this, fast DC post contingency states may vary for buses disconnected from main connected component, depending on which elements were selected
LinkedHashSet<AbstractComputedElement> breakingConnectivityElements = modifyingConnectivityCandidates.stream()
.filter(element -> isBreakingConnectivity(connectivity, element))
.collect(Collectors.toCollection(LinkedHashSet::new));
if (!breakingConnectivityElements.isEmpty()) {
// only compute for factors that have to be computed for this contingency lost
Set<String> elementsToReconnect = computeElementsToReconnect(connectivity, breakingConnectivityElements);
int createdSynchronousComponents = connectivity.getNbConnectedComponents() - 1;
Set<LfBus> disabledBuses = connectivity.getVerticesRemovedFromMainComponent();
Set<LfHvdc> hvdcsWithoutPower = PropagatedContingency.getHvdcsWithoutPower(lfNetwork, disabledBuses, connectivity);
connectivityAnalysisResult = new ConnectivityAnalysisResult(contingency, lfNetwork, elementsToReconnect,
new DisabledElements(disabledBuses, connectivity.getEdgesRemovedFromMainComponent(), hvdcsWithoutPower),
connectivity.getConnectedComponent(lfNetwork.getSlackBus()), createdSynchronousComponents, lfActions);
}
} finally {
connectivity.undoTemporaryChanges();
}
return connectivityAnalysisResult;
}
private static boolean isBreakingConnectivity(GraphConnectivity<LfBus, LfBranch> connectivity, AbstractComputedElement element) {
LfBranch lfBranch = element.getLfBranch();
return connectivity.getComponentNumber(lfBranch.getBus1()) != connectivity.getComponentNumber(lfBranch.getBus2());
}
/**
* Given the elements breaking the connectivity, extract the minimum number of elements which reconnect all connected components together
*/
private static Set<String> computeElementsToReconnect(GraphConnectivity<LfBus, LfBranch> connectivity, Set<AbstractComputedElement> breakingConnectivityElements) {
Set<String> elementsToReconnect = new LinkedHashSet<>();
// We suppose we're reconnecting one by one each element breaking connectivity.
// At each step we look if the reconnection was needed on the connectivity level by maintaining a list of grouped connected components.
List<Set<Integer>> reconnectedCc = new ArrayList<>();
for (AbstractComputedElement element : breakingConnectivityElements) {
int cc1 = connectivity.getComponentNumber(element.getLfBranch().getBus1());
int cc2 = connectivity.getComponentNumber(element.getLfBranch().getBus2());
Set<Integer> recCc1 = reconnectedCc.stream().filter(s -> s.contains(cc1)).findFirst().orElseGet(() -> new HashSet<>(List.of(cc1)));
Set<Integer> recCc2 = reconnectedCc.stream().filter(s -> s.contains(cc2)).findFirst().orElseGet(() -> Set.of(cc2));
if (recCc1 != recCc2) {
// cc1 and cc2 are still separated:
// - mark the element as needed to reconnect all connected components together
// - update the list of grouped connected components
elementsToReconnect.add(element.getLfBranch().getId());
reconnectedCc.remove(recCc2);
if (recCc1.size() == 1) {
// adding the new set (the list of grouped connected components is not initialized with the singleton sets)
reconnectedCc.add(recCc1);
}
recCc1.addAll(recCc2);
}
}
if (reconnectedCc.size() != 1 || reconnectedCc.get(0).size() != connectivity.getNbConnectedComponents()) {
LOGGER.error("Elements to reconnect computed do not reconnect all connected components together");
}
return elementsToReconnect;
}
private static Map<String, ComputedContingencyElement> createContingencyElementsIndexByBranchId(List<PropagatedContingency> contingencies,
LfNetwork lfNetwork, EquationSystem<DcVariableType, DcEquationType> equationSystem) {
Map<String, ComputedContingencyElement> contingencyElementByBranch =
contingencies.stream()
.flatMap(contingency -> contingency.getBranchIdsToOpen().keySet().stream())
.map(branch -> new ComputedContingencyElement(new BranchContingency(branch), lfNetwork, equationSystem))
.filter(element -> element.getLfBranchEquation() != null)
.collect(Collectors.toMap(
computedContingencyElement -> computedContingencyElement.getElement().getId(),
computedContingencyElement -> computedContingencyElement,
(existing, replacement) -> existing,
LinkedHashMap::new
));
AbstractComputedElement.setComputedElementIndexes(contingencyElementByBranch.values());
return contingencyElementByBranch;
}
public static ConnectivityBreakAnalysisResults run(DcLoadFlowContext loadFlowContext, List<PropagatedContingency> contingencies) {
// index contingency elements by branch id
Map<String, ComputedContingencyElement> contingencyElementByBranch = createContingencyElementsIndexByBranchId(contingencies, loadFlowContext.getNetwork(), loadFlowContext.getEquationSystem());
// compute states with +1 -1 to model the contingencies
DenseMatrix contingenciesStates = AbstractComputedElement.calculateElementsStates(loadFlowContext, contingencyElementByBranch.values());
// connectivity analysis by contingency
// we have to compute sensitivities and reference functions in a different way depending on either or not the contingency breaks connectivity
// a contingency involving a phase tap changer loss has to be processed separately
List<PropagatedContingency> nonBreakingConnectivityContingencies = new ArrayList<>();
List<PropagatedContingency> potentiallyBreakingConnectivityContingencies = new ArrayList<>();
// this first method based on sensitivity criteria is able to detect some contingencies that do not break
// connectivity and other contingencies that potentially break connectivity
detectPotentialConnectivityBreak(loadFlowContext.getNetwork(), contingenciesStates, contingencies, contingencyElementByBranch, loadFlowContext.getEquationSystem(),
nonBreakingConnectivityContingencies, potentiallyBreakingConnectivityContingencies);
LOGGER.info("After sensitivity based connectivity analysis, {} contingencies do not break connectivity, {} contingencies potentially break connectivity",
nonBreakingConnectivityContingencies.size(), potentiallyBreakingConnectivityContingencies.size());
// this second method process all contingencies that potentially break connectivity and using graph algorithms
// find remaining contingencies that do not break connectivity
List<ConnectivityAnalysisResult> connectivityAnalysisResults = computeConnectivityData(loadFlowContext.getNetwork(),
potentiallyBreakingConnectivityContingencies, contingencyElementByBranch, nonBreakingConnectivityContingencies);
LOGGER.info("After graph based connectivity analysis, {} contingencies do not break connectivity, {} contingencies break connectivity",
nonBreakingConnectivityContingencies.size(), connectivityAnalysisResults.size());
return new ConnectivityBreakAnalysisResults(nonBreakingConnectivityContingencies, connectivityAnalysisResults, contingenciesStates, contingencyElementByBranch);
}
/**
* Processes post contingency and operator strategy connectivity analysis result, from post contingency connectivity result.
* If there is no switching action or if the connectivity is not modified, the post contingency result is returned, as connectivity has not changed.
*/
public static ConnectivityAnalysisResult processPostContingencyAndPostOperatorStrategyConnectivityAnalysisResult(DcLoadFlowContext loadFlowContext, ConnectivityAnalysisResult postContingencyConnectivityAnalysisResult,
Map<String, ComputedContingencyElement> contingencyElementByBranch, DenseMatrix contingenciesStates,
List<LfAction> lfActions, Map<LfAction, AbstractComputedElement> actionElementsIndexByLfAction, DenseMatrix actionsStates) {
// if there is no topological action, no need to process anything as the connectivity has not changed from post contingency result
boolean hasAnyTopologicalAction = lfActions.stream().anyMatch(lfAction -> lfAction instanceof AbstractLfBranchAction<?>);
if (!hasAnyTopologicalAction) {
return postContingencyConnectivityAnalysisResult.withLfActions(lfActions);
}
LfNetwork lfNetwork = loadFlowContext.getNetwork();
PropagatedContingency contingency = postContingencyConnectivityAnalysisResult.getPropagatedContingency();
// verify if the connectivity is potentially modified, and returns post contingency connectivity result if this is not the case
boolean isConnectivityPotentiallyModified = isConnectivityPotentiallyModifiedByContingencyAndOperatorStrategy(lfNetwork, new States(contingenciesStates, actionsStates), contingency,
contingencyElementByBranch, lfActions, actionElementsIndexByLfAction, loadFlowContext.getEquationSystem());
if (!isConnectivityPotentiallyModified) {
return postContingencyConnectivityAnalysisResult.withLfActions(lfActions);
}
// compute the connectivity result for the contingency and the associated actions
ConnectivityAnalysisResult postContingencyAndOperatorStrategyConnectivityAnalysisResult = computeConnectivityAnalysisResult(lfNetwork, contingency,
contingencyElementByBranch, lfActions, actionElementsIndexByLfAction);
LOGGER.info("After graph based connectivity analysis, the contingency and associated actions {} break connectivity",
postContingencyAndOperatorStrategyConnectivityAnalysisResult != null ? "" : "do not");
return postContingencyAndOperatorStrategyConnectivityAnalysisResult;
}
}