Wyniki wyszukiwania - BazTech

1

Optimization of linear functions on a cyclic permutation. Based on the random search

Grebennik I., Baranov O., Chorna A., Gorbacheva E.

ECONTECHMOD : An International Quarterly Journal on Economics of Technology and Modelling Processes

|

2016

|

Vol. 5, No 3

211--216

EN

For creating adequate mathematical models of combinatorial problems of constructing optimal cyclic routes, mathematical modeling and solving a number of planning and control tasks solutions of optimization problems on the set of cyclic permutations are required. Review of the publications on combinatorial optimization demonstrates that the optimization problem on the cyclic permutations have not been studied sufficiently. This paper is devoted to solving optimization problem of a linear function with linear constraints on the set of cyclic permutations. For solving problems of this class using of known methods, taking into account the properties of a combinatorial set of cyclic permutations, is proposed. For this purpose we propose a method based on the ideology of random search. Heuristic method based on the strategy of the branch and bound algorithm is proposed to solve auxiliary optimization problem of a linear function without constraints on the set of cyclic permutations. Since application of the branch and bound algorithm immediately leads to an exponential growth of the complexity with increasing the dimension of the problem a number of modifications are suggested. Modifications allow reducing computational expenses for solving higher dimension problems. The effectiveness of the proposed improvements is demonstrated by computational experiments.

2

The branch and bound algorithm improvement in divisible load scheduling with result collection on heterogeneous systems by new heuristic function

Fard F. N., Mohammadi S., Parvizi P.

Journal of Automation Mobile Robotics and Intelligent Systems

|

2012

|

Vol. 6, No. 3

47-50

EN

In this paper we propose a new heuristic function for branch and bound algorithm. By this function we can increase the efficiency of branch and bound algorithm. Divisible loads represent computations which can be arbitrarily divided into parts and performed independently parallel. The scheduling problem consists in distributing the load in a heterogeneous system taking into account communication and computation times, so that the whole processing time is as short as possible. Since our scheduling problem is computationally hard, we propose a branch & bound algorithm. By simulating and comparing results it is observed which this result produces better answers than other methods, it means that branch and bound algorithm have less total average of relative error percentage in the variety Heuristic functions.

3

A Threshold for a Polynomial Solution of #2SAT

De Ita G., Marcial-Romero J. R., Hernandez J. A.

Fundamenta Informaticae

|

2011

|

Vol. 113, nr 1

63-77

EN

The #SAT problem is a classical #P-complete problem even for monotone, Horn and two conjunctive formulas (the last known as #2SAT). We present a novel branch and bound algorithm to solve the #2SAT problem exactly. Our procedure establishes a new threshold where #2SAT can be computed in polynomial time. We show that for any 2-CF formula F with n variables where #2SAT(F) . p(n), for some polynomial p, #2SAT(F) is computed in polynomial time. This is a new way to measure the degree of difficulty for solving #2SAT and, according to such measure our algorithm allows to determine a boundary between ‘hard’ and easy’ instances of the #2SAT problem.

4

The Branch and Bound Algorithm for joint optimization of primary and Backup routes in Survivable Networks

Walkowiak K.

Archiwum Informatyki Teoretycznej i Stosowanej

|

2003

|

T. 15, z. 4

273-296

EN

Survivability of computer networks is an important subject. Organizational and individual users of computer network expect reliable services with guarantees of data delivery. In high-speed network technologies like Asynchronous Transfer Mode (ATM) and Multiprotocol Label Switching (MPLS) a large amount of data can be lost due to a network failure and cause significant economics loses. In this work we focus on problems of network survivability. Several network restoration methods are presented and discussed. A new optimization problem of Joint Primary and Backup Routes Assignment is formulated. As the rerouting strategy the local-destination rerouting is applied. The function of lost flow due to a failure of any single link is used as an objective function. The problem of finding the optimal assignment of connections in NP-complete. Therefore we develop an exact algorithm based on the branch and bound approach. Moreover two heuristic algorithms are proposed. Numerical results are included.

PL

Przeżywalność sieci komputerowych jest ważnym zagadnieniem. Użytkownicy indywidualni i instytucjonalni oczekują niezawodnych usług gwarantujących dostarczenie przesyłanych danych. W szybkich sieciach komputerowych takich jak ATM ( Asynchronous Transfer Mode) oraz MPLS (Multiprotocol Label Switching) wiele ważnych i cennych informacji może być utraconych wskutek awarii. W tej pracy koncentrujemy się na zagadnieniach przeżywalności sieci komputerowych. Przedstawiono i porównano kilka metod zapewniania przeżywalności w sieciach. Nowy problem optymalizacyjny równoczesnego wyznaczania tras podstawowych i zapasowych został sformułowany. Jako metodę restoracji sieci po awarii wybrano restorację lokalno-globalną. Funkcja utraconego przepływu po awarii pojedynczego łącza została użyta jako funkcja kryterialna. Rozważany problem jest NP.-zupełny. Dlatego zaproponowano algorytm dokładny oparty na metodzie podziału i oszacowań. Dodatkowo przedstawiono dwa algorytmy przybliżone. Dołączono wyniki eksperymentów obliczeniowych.

5

The branch and bound algorithm for a backup virtual path assignment in survivable atm networks

Walkowiak K.

International Journal of Applied Mathematics and Computer Science

|

2002

|

Vol. 12, no 2

257-267

EN

Issues of network survivability are important, since users of computer networks should be provided with some guarantees of data delivery. A large amount of data may be lost in high-speed Asynchronous Transfer Mode (ATM) due to a network failure and cause significant economic loses. This paper addresses problems of network survivability. The characteristics of virtual paths and their influence on network restoration are examined. A new problem of Backup Virtual Path Routing is presented for the local-destination rerouting strategy. The function of the flow lost due to a failure of a single link is chosen as the performance index. The problem of finding the optimal virtual path assignment is NP-complete. Therefore we develop an exact algorithm based on the branch and bound approach. Moreover, two heuristic algorithms are proposed. Numerical results are presented.

6

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

Oprzędkiewicz I.

Archiwum Energetyki

|

2001

|

T. 30, nr 1/2

3-18

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.