Wyniki wyszukiwania - BazTech

1

Optimisation of telecommunications transport networks

Tomaszewski A.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2013

|

z. 189

9-190

EN

This monograph is devoted to optimisation models and algorithms for designing contemporary telecommunications transport networks. The particular focus is on the conceptual framework of transport network design and on the decomposition of the design problem and the design process. The presented conceptual framework is based on an original layered model of network resources, which is consistent with the functional architecture of transport networks contained in the ITU-T standards as well as can be directly expressed using mathematical models of multicommodity flow networks. The framework introduces an abstract generic model of the transport network design problem, its decomposition with respect to network layers and States, and an abstract generic network design procedure of solving the problem. The framework encompasses the models of the physical architecture and the organisational structure of the transport network. and the model of the network planning process. The presented work introduces an original complete mathematical description of the transport network based on the multicommodity network flow model complemented with elements pertaining to the notions of layers and states. Also, an original extension of the classical necessary and sufficient conditions of the existence of a multicommodity flow to the case of multiple layers and multiple slates is described. It is shown how the basic network model can be extended and generalised to consistently tackle fundamental phenomena and mechanisms of transport network operations related to traffic routing, network resilience to failures, quality of service and equitable allocation of network resources, variations and uncertainty of traffic demands, and network evolution. Applications of the basic methods of mathematical programming that are commonly used for network design are analysed in detail. In particular, the work analyses the branch-and-bound approach, the cutting plane method, the column generation and the constraint generation techniques of mixed integer linear programming, problem decomposition methods based on Benders' decomposition and Lagrangian relaxation, and the lesicographic maximization and max-min fair optimisation methods of multiple criteria decision making, The usage of the methods is analysed by means of original studies of difficult network optimization problems such as shortest-path routing design, connection restoration design in GMPLS networks, inter-domain traffic routing optimisation, and minimisation of label usage in GMPLS networks. A particularly important theoretical element of this work is a comprehensive analysis and classification of the complexity of designing transport networks resilient to failures. Original proofs of the NP-hardness of the resilient network design are presented that pertain to all major variants of the problem, in particular, providing a final answer to a number of so-far unresolved questions.

PL

Przedmiotem pracy są modele i algorytmy projektowania współczesnych telekomunikacyjnych sieci transportowych. Szczególną uwagę poświecono kwestii modelu pojęciowego problemu projektowania sieci oraz zagadnieniom dekompozycji problemu i procesu projektowania. Zaproponowany w pracy model pojęciowy jest oparty na oryginalnym warstwowym modelu zasobów sieci transportowej, który jest zgodny z podstawową architekturą funkcjonalną sieci transportowej zawartą w standardach 1TU-T poświęconych zagadnieniom sterowania i zarządzania sieciami, a jednocześnie może być wyrażony wprost poprzez modele optymalizacyjne sieci przepływów wielotowarowych. Elementami modelu pojęciowego są również model abstrakcyjnego generycznego problemu projektowania sieci transportowej dekomponowalnego wzglądem warstw i stanów sieci oraz abstrakcyjna generyczna procedura projektowania wielowarstwowej wielostanowej sieci transportowej. Uzupełnieniem modelu pojęciowego są modele architektury fizycznej i struktury organizacyjnej sieci transportowej, oraz model procesu planowania sieci. W pracy przedstawiono oryginalny kompletny opis matematyczny sieci transportowych oparty na modelu sieci przepływów wielotowarowych, uzupełnionym o pojęcia wielowarstwowości i wielostanowości. Zaprezentowano oryginalne rozszerzenie klasycznych warunków koniecznych i dostatecznych istnienia przepływu wielotowarowego na przypadek wielu warstw i wielu stanów sieci. Pokazano jak poprzez ograniczone rozszerzenia lub uogólnienia podstawego matematycznego opisu siec: jest możliwe jednolite zamodelowanie podstawowych zjawisk i mechanizmów działania sieci transportowej, związanych w szczególności z kierowaniem ruchu, zabezpieczeniem sieci przed awariami, zapewnieniem jakości obsługi ruchu i sprawiedliwym wykorzystaniem zasobów, zmiennością i niepewnością zapotrzebowani ruchowych oraz ewolucją sieci w czasie. Praca analizuje sposoby wykorzystania najważniejszych metod programowania matematycznego, w szczególności optymalizacji dyskretnej, stosowanych w projektowaniu sieci transportowych: metod programowania liniowego całkowitoliczbowego - metody podziałów i ograniczeń, metody płaszczyzn odcinających; metod dekompozycji - metody dekompozycji Bendersa, metody relaksacji Lagrange'a; metod optymalizacji wielokryterialnej – metod maksymalizacji leksykograficznej t optymalizacji sprawiedliwej. Przedstawiono oryginalne wykorzystanie tych metod w trudnych problemach projektowania sieci, takich jak problem kierowania ruchu po najkrótszych ścieżkach, problem projektowania sieci GMPLS zabezpieczonych mechanizmem Fast Reroute, problem kierowania ruchu międzydomenowego czy problem minimalizacji liczby etykiet w sieci GMPLS. Szczególnym elementem teoretycznym pracy jest wyczerpująca analiza i klasyfikacja złożoności problemów projektowania sieci zabezpieczonych przed awariami, której wynikiem jest zbiór oryginalnych dowodów NP-zupełność i wszystkich podstawowych wariantów problemu projektowania, w szczególności w części do niedawna nierozstrzygniętych.

2

Algebraic approach for model decomposition: Application to fault detection and isolation in discrete-event systems

Berdjag D., Cocquempot V., Christophe C., Shumsky A., Zhirabok A.

International Journal of Applied Mathematics and Computer Science

|

2011

|

Vol. 21, no 1

109-125

EN

This paper presents a constrained decomposition methodology with output injection to obtain decoupled partial models. Measured process outputs and decoupled partial model outputs are used to generate structured residuals for Fault Detection and Isolation (FDI). An algebraic framework is chosen to describe the decomposition method. The constraints of the decomposition ensure that the resulting partial model is decoupled from a given subset of inputs. Set theoretical notions are used to describe the decomposition methodology in the general case. The methodology is then detailed for discrete-event model decomposition using pair algebra concepts, and an extension of the output injection technique is used to relax the conservatism of the decomposition.

3

Algorytm obliczeń równoległych dla przestrzennego modelu walcowania stali ze strefą półciekłą

Dębiński T., Głowacki M., Jędrzejczyk D., Gumuła A.

Hutnik, Wiadomości Hutnicze

|

2010

|

Vol. 77, nr 4

181-185

PL

Metoda elementów skończonych jest szeroko stosowana do modelowania zjawisk fizycznych, w tym procesów odkształcania metali. Ze względu na złożoność zjawisk fizycznych zachodzących podczas takich procesów zachodzi konieczność stosowania skomplikowanych modeli matematycznych umożliwiających opisanie zachowania się metalu z zadowalającą dokładnością. Istotnym aspektem modelowania zjawisk jest nie tylko symulacja zachowania się samego materiału w czasie procesu, ale również dążenie do kontrolowania parametrów procesu w zakresie umożliwiającym uzyskanie wyrobu o jak najlepszych parametrach użytkowych. Jednym z takich zastosowań jest sterowanie procesem dogniatania pasma ze strefą półciekłą, tzw. „soft reduction”. Ze względu na charakterystykę procesu ciągłego odlewania stali niewielkie zmiany parametrów mogą mieć zasadniczy wpływ na całość procesu z zatrzymaniem produkcji włącznie. Wykorzystanie modelu matematycznego wraz z metodą elementów skończonych dostarcza informacji opisujących ww. proces. Aby wyniki odzwierciedlały rzeczywistość w sposób zadowalający, niezbędne jest zastosowanie wystarczającej dokładności obliczeń. Wiąże się to z koniecznością generowania gęstej siatki elementów skończonych. Powoduje to powstawanie dużych układów równań. Ze względu na ograniczoną ilość pamięci operacyjnej komputerów, obliczenia z bardzo dużą dokładnością mogą okazać się niemożliwe do wykonania lub czas potrzebny na uzyskanie wyników będzie zbyt długi. W celu wyeliminowania tego ograniczenia stosuje się superkomputery lub klastry o dużej liczbie komputerów połączonych szybką siecią. Drugie z wymienionych rozwiązań jest szeroko stosowane ze względów ekonomicznych, w tym dostępności odpowiedniego sprzętu komputerowego, jak również ze względu na uzyskiwane moce obliczeniowe. Jedną z szeroko stosowanych technologii dla klastrów jest interfejs przesyłania komunikatów. Wykorzystując tę technologię problem symulacji walcowania ze strefą półciekłą można przyspieszyć poprzez równoległe rozwiązanie układów równań powstałych w wyniku dyskretyzacji przy użyciu MES, jak również poprzez dekompozycję sieci elementów skończonych i dystrybucję komponentów pomiędzy dostępne procesory. Niniejsza praca przedstawia problem symulacji procesu walcowania pasma ze strefą półciekłą. Obliczenia równoległe wykorzystano ze względu na konieczność uzyskania wyników z wysoką dokładnością w krótkim czasie. Dokonano optymalnej dekompozycji sieci elementów skończonych w celu zminimalizowania obciążenia węzłów obliczeniowych oraz dekompozycji pasmowej uzyskanego układu równań.

EN

The finite element method is very often applied to modelling of physical phenomena – among them metal deformation. Taking into account the complexity of physical phenomena accompanying steel deformation the mathematical models should ensure acceptable precision. A very important aspect of the simulation is not only the metal behaviour but also the control of process parameters leading to the best product. One of the processes which strongly require controlled deformation is the so called “soft reduction” of plates with mushy zone. In case of casting process small changes of input parameters may have large effect on whole process. Application of appropriate mathematical model and right finite element discretization is very helpful and is a source of information important for both the casting and the integrated casting and rolling technologies. Acceptable computing precision is required to guarantee the process reliability. To achieve high precision of calculations a high density mesh must be generated. Hence, the solution of large set of equations is required. Because the operating memory of a single computer is limited, the computing with high precision may be impossible or the computation time may be too long. To eliminate this restriction a supercomputer or a cluster of a number of computers working within fast net have to be used. The latter possibility is often the preferred one as it is less expensive, easily accessible and provides a high computing power. One of the widely used methods for cluster component cooperation is the application of message passing interface. With this technology the simulation of mushy steel rolling can be performed in parallel way in both the cases: parallel solution of equation set and decomposition of the mesh between available processors. The current paper is dedicated to the simulation of rolling of steel plates with mushy zone. Requirements concerning both high precision results and short computation time necessitate application of parallel computing. For proper load balancing an optimization of the decomposition has been done.