Wyniki wyszukiwania - BazTech

1

A formal approach to Menger's theorem

Bonacina Roberta, Misselbeck-Wessel Daniel

Reports on Mathematical Logic

|

2022

|

Vol. 57

45--51

EN

Menger’s graph theorem equates the minimum size of a separating set for non-adjacent vertices a and b with the maximum number of disjoint paths between a and b. By capturing separating sets as models of an entailment relation, we take a formal approach to Menger’s result. Upon showing that inconsistency is characterised by the existence of sufficiently many disjoint paths, we recover Menger’s theorem by way of completeness.

2

Metoda szybkiego wyznaczania par węzłowo-rozłącznych tras dla ochrony transmisji unicast

Myslitski K., Rak J.

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2015

|

nr 8-9

717--723

PL

W celu ochrony transmisji przed awarią węzłów/łączy wykorzystuje się alternatywne trasy transmisji. Jednakże złożoność obliczeniowa dostępnych algorytmów doboru tras rozłącznych często istotnie wstrzymuje producentów sprzętu od implementacji tychże rozwiązań. Przedstawiono nowe podejście do wyznaczania par rozłącznych tras, oparte na transformacji grafu sieci w metastrukturę. Wyniki badań dotyczące czasu wyznaczania tras pokazują istotną przewagę opisanej metody (~20%) nad podejściem referencyjnym (algorytmem) Bhandariego.

EN

Alternate (backup) paths are commonly utilized in communication networks to provide protection against failures of network nodes/links. However, computational complexity of available algorithms of disjoint paths calculation frequently prevents the vendors of network equipment from implementing such solutions. In this work, we present a new approach to disjoint paths calculation based on transformation of the original network graph into the respective meta-structure. Results of analysis referring to the computational time show a significant advantage of our method (about 20%), compared to the respective characteristics of the reference Bhandari's algorithm.

3

Zastosowanie metod wyznaczania przepływu w sieciach do planowania manewru wojsk

Tarapata Z.

Biuletyn Instytutu Systemów Informatycznych

|

2008

|

nr 2

31-44

PL

W artykule przedstawiono opis sposobu wykorzystania metod wyznaczania przepływu w sieciach do rozwiązania specyficznego problemu planowania manewru wojsk. Zdefiniowano model sieci formalnej, bazującej na danych z cyfrowej mapy terenu, wykorzystywanej jako model środowiska w problemie planowania manewru. Sformułowano optymalizacyjny problem planowania przegrupowania K obiektów z rejonu startowego (reprezentowanego przez podzbiór wierzchołków sieci formalnej) do rejonu docelowego, z dodatkowym ograniczeniem na rozłączność dróg. Opisano sposób modyfikacji sieci pierwotnej oraz poszukiwania jednego z rozwiązań dopuszczalnych sformułowanego problemu planowania przegrupowania z użyciem metody znajdowania przepływu maksymalnego w sieci zmodyfikowanej. Przedyskutowano metodę poszukiwania rozwiązania optymalnego bazującą na algorytmie znajdowania przepływu zaspokajającego o minimalnym koszcie w pewnej sieci zastępczej. Opisane metody zilustrowano przykładami obliczeniowymi. Oszacowano złożoność obliczeniową prezentowanych algorytmów. Artykuł kończy omówienie rozszerzeń sformułowanego problemu wyjściowego oraz metod ich rozwiązywania.

EN

In the paper an application of methods for determining flows in networks to military forces maneuver planning is presented. Model of formal network as environment model for manoeuvre planning based on digital maps is defined. Optimization problem of redeployment planning of K objects from source region to destination one taking into account paths disjointness is considered. The method for finding one of the acceptable solution of considered redeployment problem based on method of solving maximum flow problem is described. The method for finding optimal solution of considered problem based on method of solving minimum cost network flow problem in some substitute network is defined. For both of the methods computational complexity is estimated. Some computational examples of presented methods are shown.

4

Algorytmy harmonogramowania zsynchronizowanego przemieszczania wielu obiektów

Tarapata Z.

Badania Operacyjne i Decyzje

|

2008

|

nr 4

107-132

PL

W pracy przedstawiono algorytmy wyznaczania harmonogramu zsynchronizowanego przemieszczania wielu obiektów. Zdefiniowano problem harmonogramowania przemieszczania w postaci dwukryterialnego nieliniowego zadania optymalizacji. Omówiono sposób rozwiązania sformułowanego problemu dwukryterialnego poprzez poszukiwanie rozwiązania leksykograficznego. Podano dwa algorytmy harmonogramowania zsynchronizowanego przemieszczania wielu obiektów oraz opisano ich własności. Szczegółowo omówiono konieczne i wystarczające warunki umożliwiające otrzymanie rozwiązania optymalnego. Oszacowano złożoności obliczeniowe prezentowanych algorytmów oraz przedyskutowano ich własności. Zasadę działania algorytmów zilustrowano przykładami.

EN

The paper presents algorithms of determining a synchronized movement schedule of many objects. The author defines movement scheduling as a bicriterion nonlinear optimization problem. He also presents a method of solving the bicriterion problem which is based on finding a lexicographic solution. Two scheduling algorithms of synchronized movement and their properties are given. The first algorithm is based on the dynamic programming, the second one is based on the cost-profit analysis. The necessary and sufficient conditions for obtaining optimal solutions from the algorithms are discussed in detail. The author describes computational complexity and some properties of the algorithms. The idea of the algorithms is presented with a few examples.

5

Modele harmonogramowania zsynchronizowanego przemieszczania wielu obiektów

Tarapata Z.

Badania Operacyjne i Decyzje

|

2007

|

nr 2

83-1031

PL

W artykule przedstawiono problem wyznaczania harmonogramu zsynchronizowanego przemieszczania wielu obiektów, wykorzystywany w zagadnieniach: routingu w sieciach komputerowych, planowania przemieszczania mobilnych robotów, przetwarzania zadań w systemach równoległych (rozproszonych), sterowania ramionami wielu niezależnych robotów, planowania i synchronizacji przemieszczania wielu obiektów w symulacyjnych grach komputerowych (systemy typu CGF i SAF). Omówiono szereg modeli harmonogramowania przemieszczania. Zdefiniowano dwie grupy kryteriów istotnych z punktu widzenia oceny harmonogramu: kryteria związane z szybkością przemieszczania obiektów oraz z „równoległością” ich przemieszczania (w sensie położenia i czasu osiągnięcia pewnych punktów pośrednich). Skupiono się na sformułowaniu nieliniowego zadania harmonogramowania przemieszczania obiektów w celu minimalizacji sumy opóźnień w tzw. punktach wyrównania, przy pewnych dodatkowych ograniczeniach. Przedstawiono również dwa równorzędne sformułowania problemu w postaci dwukryterialnych zadań programowania matematycznego. Wykazano, że macierz współczynników ograniczeń w tych zadaniach jest całkowicie unimodularna, co umożliwia zastosowanie efektywnych algorytmów rozwiązywania zadań programowania liniowego, przy poszukiwaniu leksykograficznego rozwiązania problemu dwukryterialnego. Omówiono podobieństwa i różnice między sformułowanym problemem harmonogramowania, a klasycznym problemem szeregowania zadań przed liniami krytycznymi w celu minimalizacji maksymalnego opóźnienia zadań. Zdefiniowano wiele rozszerzeń omawianego problemu. Jako jedno z nich opisano problem planowania przemieszczania wielu obiektów zgodnie z pewnym wzorcem ugrupowania. Zarysowano sposoby rozwiązywania sformułowanych problemów harmonogramowania.

EN

The paper deals with the problem of determining movement schedule of many objects, used in many domains such as: routing in computer networks, movement planning of mobile robots, tasks processing in parallel or distributed computing systems, arms control of independent robots, planning and synchronization of the movement of many objects in computer simulation games (e.g. in Computer Generated Forces (CGF) systems or Semi-Automated Forces (SAF) systems). A lot of movement scheduling models are discussed. Two groups of criteria which are essential from the point of view of schedule estimation are described: a group connected with movement time of all objects and a group connected with “parallelization” of their movement (in the sense of location and times of reaching specified checkpoints). A nonlinear movement scheduling problem in order to minimize the sum of delays of all objects at checkpoints with some additional constraints is defined. Two equivalent formulations of two-criteria mathematical programming problems are also presented. It is proved that constraint coefficient matrices for both problems are totally unimodular and we can use effective algorithms for solving linear programming problems to find lexicographic solution of two-criteria problems. Similarities and differences between the defined problem and classical tasks scheduling problem before critical lines on parallel processors are discussed. Some extensions of the problem are presented. One of which is the scheduling movement problem of many objects according to a group pattern. Methods of solving formulated problems are indicated.