Application of intelligent search strategy in the branch and bound method with the use of the example of cost optimization for an electric power network with high load variability

• Autorzy: Oprzędkiewicz I.

Warianty tytułu

PL

Zastosowanie strategii inteligentnego przeszukiwania w metodzie podziału i ograniczeń na przykładzie zagadnienia optymalizacji kosztów sieci elektroenergetycznej o dużej zmienności obciążenia

• Języki publikacji: EN

Abstrakty

EN

Cost optimization for losses in an electric power network with high load variability is a NP-hard. In problems of this category it is of relevance to devise effective algorithms, which will enable us to promptly find a solution. Obtaining a precise solution in this case is very difficult, since even a minor growth of the problem's volume results in an exponential increase in the calculation time. The chief method in search of optimal solutions to NP-hard problems is the branch and bound method. The paper deals with an analysis of effectiveness improvement formulae of the algorithm based on that method, through the reduction of the search path in the sub-problem tree. A method has been presented, in which the decision to select the sub-problem for analysis depends on the hitherto course of calcultions. As a criterion for this selection the assessment of the usability of the defined selection principles has been assumed (closely related with the problem being resolved). The algorithm is complimented by a meta-heuristics module, which is used to improve the currently known as the best solution.

PL

Optymalizacja kosztów strat w sieci elektroenergetycznej o dużej zmienności obciążenia jest zagadnieniem NP-trudnym. W problemach tej klasy duże znaczenie ma opracowanie efektywnych algorytmów, które pozwalają szybko znaleźć rozwiązanie. Uzyskanie rozwiązania dokładnego jest w tym przypadku bardzo trudne, gdyż niewielki wzrost rozmiaru problemu powoduje wykładniczy wzrost czasu obliczeń. Podstawową metodą poszukiwania optymalnych rozwiązań problemów NP-trudnych jest metoda podziału i ograniczeń. W pracy zajęto się badaniem i analizą metod poprawy efektywności algorytmu opartego na tej metodzie poprzez skrócenie drogi przeszukiwania w drzewie podproblemów. Przedstawiono metodę, w której decyzja o wyborze podproblemu do analizy zależy od dotychczasowego przebiegu obliczeń. Jako kryterium wyboru przyjęto ocenę przydatności zdefiniowanych reguł wyboru (ściśle związanych z rozwiązywanym zagadnieniem). Algorytm uzupełniono dodatkowym modułem zawierającym metaheurystykę i wspomagającym proces wyznaczania wartości odcinających.

Słowa kluczowe

EN

electric power network; cost optimization; NP-hard; branch and bound algorithm

PL

optymalizacja strat; sieci elektroenergetyczne; problem NP-trudny; metoda podziału i ograniczeń

• Wydawca: Wydawnictwo Instytutu Maszyn Przepływowych PAN ; Komitet Problemów Energetyki Polskiej Akademii Nauk
• Czasopismo: Archiwum Energetyki
• Rocznik: 2001
• Tom: T. 30, nr 1/2
• Strony: 3--18
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Oprzędkiewicz I.

• Akademia Górniczo-Hutnicza w Krakowie