Comparing two pricing methods for path generation in a resilient network design problem

• Autorzy: Kalesnikau I.

Identyfikatory

DOI

10.15199/59.2017.8-9.52

Warianty tytułu

PL

Porównanie dwóch metod generacji ścieżek dla problemu wymiarowania sieci odpornych na awarie

• Konferencja: XXXIII Krajowe Sympozjum Telekomunikacji i Teleinformatyki (XXXIII ;13-15.09.2017 ; Warszawa, Polska)
• Języki publikacji: EN

Abstrakty

EN

Global rerouting (GR) is a benchmark traffic routing and protection strategy for resilient communication networks that minimizes the protection capacity cost. In case of failure, GR restores traffic demands in the surviving link capacity from scratch, no matter how the nominal traffic flows have been routed. The considered optimization problem related to GR is formulated as a non-compact link-path linear program and as such requires path generation. The paper compares two versions of the pricing problem – an essential part of the path generation algorithm.

PL

Global rerouting (GR) jest strategią trasowania i zabezpieczania ruchu w sieciach telekomunikacyjnych, która minimalizuje koszt pojemności łączy wymaganej do odtwarzania przepływów. W przypadku awarii, GR realizuje przepływy w aktualnie dostępnych pojemnościach łączy od nowa, niezależnie od tego, jak te przepływy były trasowane przed awarią. Związany z GR problem optymalizacyjny jest sformułowany w postaci niezwartego programu liniowego typu łącze-ścieżka, który wymaga generacji ścieżek. W referacie porównane są dwie wersji tzw. pricing problem – podstawowej części algorytmu generacji ścieżek.

Słowa kluczowe

EN

mixed-integer programming; multiple partial link failures; path generation; resilient network design

PL

programowanie całkowitoliczbowe; wielokrotne awarie łączy; generacja ścieżek; wymiarowanie sieci odpornych na awarie

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
• Rocznik: 2017
• Tom: nr 8-9
• Strony: 882--885, CD
• Opis fizyczny: Bibliogr. 7 poz., tab.

Twórcy

autor

Kalesnikau I.

• Institute of Telecommunications, Warsaw University of Technology, ul. Nowowiejska 15/19, 00-665 Warszawa

Bibliografia

• [1] Orlowski S. and Pióro M., 2012. “Complexity of column generation in network design with pathbased survivability mechanisms”, Networks, 59(1):132–147.
• [2] Minoux. M., 1986. “Mathematical Programming: Theory and Algorithms”, John Wiley& Sons.
• [3] Lasdon L., 1970. “Optimization Theory for Large Systems”, MacMillan.
• [4] Pióro M., Fouquet Y., Nace D. and Poss M., 2016. “Optimizing flow thinning protection in multicommodity networks with variable links capacity.”, Operations Research, 64(2):273–289.
• [5] Pióro M., Kalesnikau I. and Poss M., 2017. „Path Generation for Affine Flow Thinning”, INOC 2017, Lisbon.
• [6] Pióro M. and Medhi D., 2004. „Routing, Flow, and Capacity Design in Communication”, Morgan- Kaufmann Publishers.
• [7] Orlowski S., Wessaly R., Pióro M. and Tomaszewski A., 2010. “SNDlib 1.0 – survivable network design library”, Networks, 55(3):276–286.