November 19, 2024
15:00
CORE B.-135
Dimitri Watel (SAMOVAR).
Invited by Daniele Catanzaro
will give a presentation on :
Optimization of electrical network configuration : complexity and approximability
Abstract :
In an electric network, the electric flow is not freely chosen by the operator. It results from the power demands made by consumers and the network's topology. By knowing these two parameters, one can deduce the value of the flow in each cable of the network. We assume a simplified model where the demand at each node is equally distributed in each input arc. The operator can influence the network using two parameters: by disabling one or more nodes or by forcing the direction of the electric current. Once these actions are decided, the operator can estimate the flow value throughout the network. The operator's goal is to avoid overloading the electric sources, as this could lead to their failure and consequently overload other sources. With this snowball effect, the operator risks a total blackout. One way to prevent this phenomenon is to optimize the load reserve. The load of a source is the percentage of its production capacity that is being utilized, which must remain well below 100% to avoid overload. The load reserve is the difference between the maximum load and the minimum load of all sources combined. Therefore, a balanced network is one where all sources are utilized at the same percentage. This type of optimization also ensures equitable revenue when the energy-producing entities do not all have the same production capacity. Our problem can be described as follows: given an electric network and the load calls from consumers, what are the deactivation and orientation actions that the operator should take to minimize the load reserve? In this problem, we are interested in the complexity and approximability of this issue. We demonstrate that this problem is NP-Hard and inapproximable in general. It remains NP-Hard even in the case where the electric network is a tree; however, in this case, there exists an approximation scheme with an absolute approximation ratio. The end of the presentation will address the challenges of generating realistic instances and evaluating these algorithms.