Wyniki wyszukiwania - BazTech

1

Organizacja przewozów drobnicy koleją

Cisowski T., Stokłosa J.

Logistyka

|

2014

|

nr 3

1128--1140

PL

W artykule przedstawiono organizację przewozów ładunków w pojedynczych wagonach lub grupach wagonów. Autorzy zaprezentowali optymalną organizację tych przewozów, opartą na metodzie podziału i ograniczeń. Pokazali model matematyczny oraz algorytm budowy optymalnego planu zestawiania pociągów, bazując na tej metodzie. Przytoczyli przykład wyznaczania optymalnego planu zestawienia pociągów metodą podziału i ograniczeń dla rzeczywistych potoków wagonów. W podsumowaniu podkreślili zalety stosowanej organizacji przewozów drobnicy przy występowaniu ograniczeń, związanych z zasobami.

EN

An organization of general cargo transportation in the individual cars or in the groups of cars has been described in the paper. The authors have presented a method of the optimal organization of these transport based on the division and limitation method. The mathematical model as well as the algorithm of the optimal plan of the trains forming basing on this method has been shown. An example of the determining of the optimum plan of composition of trains using the methods of division and the limitation for real streams of cars has been presented. In the recapitulation the authors underlined the advantage of the proposed organization of transport of the general cargo under condition of the limitations connected with supplies.

2

Accelerating backtrack search with a best-first-search strategy

Mann Z. Á., Szép T.

International Journal of Applied Mathematics and Computer Science

|

2014

|

Vol. 24, no. 4

901--916

EN

Backtrack-style exhaustive search algorithms for NP-hard problems tend to have large variance in their runtime. This is because “fortunate” branching decisions can lead to finding a solution quickly, whereas “unfortunate” decisions in another run can lead the algorithm to a region of the search space with no solutions. In the literature, frequent restarting has been suggested as a means to overcome this problem. In this paper, we propose a more sophisticated approach: a best-first-search heuristic to quickly move between parts of the search space, always concentrating on the most promising region. We describe how this idea can be efficiently incorporated into a backtrack search algorithm, without sacrificing optimality. Moreover, we demonstrate empirically that, for hard solvable problem instances, the new approach provides significantly higher speed-up than frequent restarting.

3

A Parallel Branch and Bound Approach to Optimal Power Flow with Discrete Variables

Moreira J. C., Míguez E., Vilachá C., Otero A. F.

Przegląd Elektrotechniczny

|

2013

|

R. 89, nr 3a

47--52

EN

An optimal power flow (OPF) with discrete variables is a non-convex, nonlinear combinatorial problem. Usually the discrete variables present in an OPF are treated as continuous variables. The solution obtained using this method is clearly infeasible, but it is considered to be close to the discrete real solution and can be attained easily without producing an excessive degradation in optimality. These hypotheses can easily be refuted by demonstrating the need for a more robust general mechanism for treating the discrete variables in the OPF. Finding the exact solution is intractable due to the high computing cost it requires--this fact causes the heuristic techniques to be seen as a natural way to obtain good solutions quickly. This article presents an algorithm based on a branch and bound technique that, with the help of the parallel computing power a personal computer (PC) provides, allows pseudo-optimal solutions to be attained with good calculating times. The numerical results obtained by applying the technique proposed in IEEE networks of 118 and 300 nodes and a real size network derived from the Spanish transport network, demonstrate that the algorithm proposed has good execution times, provides solutions close to the optimum, and naturally manages the infeasibilities that are produced during the process.

PL

Obliczenie optymalnego rozpływu mocy dla zmiennych dyskretnych jest problemem nieliniowym kombinacyjnym. Zwykle zakłada się, że zmienne dyskretne są traktowane jak zmienne ciągłe. Ta metoda uniemożliwia uzyskanie dokładnego wyniku w akceptowalnym czasie. Stąd powstało wiele technik heurystycznych, umożliwiających szybkie uzyskanie wyniku o dobrej dokładności. W artykule zaprezentowano algorytm na podstawie techniki podziału i ograniczeń, która, przy zastosowaniu obliczeń równoległych w nowoczesnych komputerach PC, pozwala na szybkie uzyskanie wyniku sub-optymalnego. Algorytm zastosowano do obliczeń sieci IEEE o 118 I 300 węzłach oraz rzeczywistej sieci, uzyskując krótkie czasy obliczeń i wyniki bliskie optymalnym.

4

Użyteczność deterministycznych metod optymalizacji globalnej do szacowania parametrów w zagadnieniach hydrologicznych

Grządziel M., Jełowicki J.

Woda-Środowisko-Obszary Wiejskie

|

2011

|

T. 11, z. 1

61-74

PL

Numeryczne metody optymalizacji, powszechnie stosowane w zagadnieniach hydrologicznych, nie gwarantują wyznaczenia minimum globalnego funkcji celu. Ich popularność wiąże się z tym, że mogą one być stosowane w zagadnieniach, w których liczba zmiennych decyzyjnych jest stosunkowo duża. W pracy dokonano przeglądu metod deterministycznych, które umożliwiają znalezienie optimum globalnego w przypadku, gdy funkcja celu ma więcej niż jedno minimum lokalne. Metody te mogą być podzielone na dwie kategorie: asymptotycznie kompletne oraz kompletne. Podczas gdy algorytmy należące do obu klas są w stanie generować ciąg rozwiązań przybliżonych zbieżny do rozwiązania zagadnienia optymalizacji globalnej, to tylko dla algorytmów należących do drugiej z wymienionych kategorii są dostępne nieheurystyczne kryteria stopu. Przykłady przedstawione w pracy ilustrują możliwości zastosowania metod asymptotycznie kompletnych do szacowania parametrów w modelach procesów hydrologicznych, takich jak: modele różniczkowe przepływu wód gruntowych, modele hydrauliczne wchodzące w skład modeli hydrodynamicznych wykorzystywanych do modelowania zasobów wód powierzchniowych, modele typu opad-odpływ czy też integralne modele zlewni.

EN

Most numerical optimization methods that are widely used in hydrology don't guarantee reaching the global minimum of the goal function. They became popular mainly due to their ability of handling relatively multi-dimensional problems. The paper reviews the deterministic methods capable of finding the global optimum in the presence of local optima. They can be divided into two categories: asymptotically complete methods and complete methods. While algorithms from both classes can generate a sequence converging to a solution of the global optimization problem, only for the algorithms from the latter class non-heuristic stopping criteria are available. The examples presented in the paper illustrate the applicability of asymptotically complete methods to parameter estimation in modelling hydrological processes, such as differential models of groundwater flow, hydraulic models embedded into hydrodynamic models of river systems, the precipitation–outflow models or integral catchment models.

5

Szeregowanie zadań o zmiennych wartościach z różnymi terminami dostępności – algorytmy rozwiązania

Janiak A., Kołodka P., Krysiak T.

Przegląd Elektrotechniczny

|

2010

|

R. 86, nr 9

91-96

PL

Praca dotyczy problemu szeregowania zadań o zmiennych wartościach i niezerowych terminach dostępności na pojedynczej maszynie. Analizowano potęgowy model wartości zadań, a jako kryterium – maksymalizację sumy wartości wszystkich zadań. Problem powyższy jest co najmniej NP-trudny. Do jego rozwiązania skonstruowano algorytm dokładny typu podziału i ograniczeń oraz szereg algorytmów heurystycznych typu konstrukcyjnego, a także jeden typu popraw. Efektywność skonstruowanych algorytmów przebadano eksperymentalnie.

EN

The paper deals with a problem of scheduling jobs with changeable job values and non-zero release dates on a single machine. A power model of job values and the criterion of maximization of the total job values are analyzed. The above problem is at least NP-hard. Thus, a branch and bound exact algorithm and some heuristic algorithms (constructive and improving type) have been developed. Their efficiency have been examined experimentally.

6

Przyspieszanie metody podziału i ograniczeń dla problemu podziału funkcjonalności na sprzęt i oprogramowanie

Strachacki M.

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

|

2008

|

T. 15

55-60

PL

Niniejsza praca przedstawia analizę wrażliwości metody podziału i ograniczeń B&B (ang. branch and bound) używanej do podziału funkcjonalności na sprzęt i oprogramowanie. Zbadano teoretyczny wpływ wszystkich parametrów B&B na czas obliczeń. Wyniki eksperymentów ujawniły, że najwrażliwszymi parametrami są: funkcja ograniczenia dolnego, reguła wyboru podproblemu, reguła podziału oraz rozwiązanie początkowe. Aby skrócić czas obliczeń metody B&B należy odpowiednio zoptymalizować parametry przy użyciu algorytmu symulowane-go wyżarzania. Testy wykazały, że dla rozmiaru problemu n = 30 uzyskano średnio 130-krotne przyspieszenie obliczeń. Opisana optymalizacja hybrydowa jest najwydajniejszą z metod dotychczas zaprezentowanych w literaturze.

EN

This paper presents sensitivity analysis of branch and bound (B&B) method used for hardware/software partitioning task. The impact of all B&B parameters on computation time is theoretically analyzed and results of experiments are presented. Results show that most sensitive parameters are a lower bound function, a selection rule, a branching rule and an initial solution. To shorten B&B computation time these parameters have to be set properly and additional preoptimization step should be applied. This pre-optimization step uses simulated annealing to set parameters in limited time. Results of experiments show that the computation time speedup x 130 is achieved on average. This hybrid optimization is the most efficient presented so far.

7

Configuring a sensor network for fault detection in distributed parameter systems

Patan M., Uciński D.

International Journal of Applied Mathematics and Computer Science

|

2008

|

Vol. 18, no 4

513-524

EN

The problem of fault detection in distributed parameter systems (DPSs) is formulated as that of maximizing the power of a parametric hypothesis test which checks whether or not system parameters have nominal values. A computational scheme is provided for the design of a network of observation locations in a spatial domain that are supposed to be used while detecting changes in the underlying parameters of a distributed parameter system. The setting considered relates to a situation where from among a finite set of potential sensor locations only a subset can be selected because of the cost constraints. As a suitable performance measure, the Ds-optimality criterion defined on the Fisher information matrix for the estimated parameters is applied. Then, the solution of a resulting combinatorial problem is determined based on the branch-and-bound method. As its essential part, a relaxed problem is discussed in which the sensor locations are given a priori and the aim is to determine the associated weights, which quantify the contributions of individual gauged sites. The concavity and differentiability properties of the criterion are established and a gradient projection algorithm is proposed to perform the search for the optimal solution. The delineated approach is illustrated by a numerical example on a sensor network design for a two-dimensional convective diffusion process.

8

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.