Naslov
Algebraic formulation and solution of robust path problems

Autori
Robert, Manger ; Ana, Klobučar

Vrsta, podvrsta i kategorija rada
Sažeci sa skupova, sažetak, znanstveni

Izvornik
EURO 2018 Program, June 29, 2018 / Vanden Berghe, Greet - Valencia : EURO - The Association of European Operational Research Societies, 2018, 103-103

Skup
29th European Conference on Operational Research (EURO 2018)

Mjesto i datum
Valencia, Španjolska, 08.07.2018. - 11.07.2018

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
Directed graph ; Path problem ; Path algebra ; Robust optimization ; Pareto efficiency

Sažetak
Path problems in graphs deal with finding shortest paths, most-reliable paths, paths of maximum capacity, etc. It is well known that various types of such problems can be treated together within a common algebraic framework. Then, each type is characterized by a different "path algebra", i.e. a different instance of the same abstract algebraic structure. In this work, robust variants of path problems are considered, where arc lengths, reliabilities or capacities are uncertain and expressed through explicitly given scenarios. It is demonstrated that the common algebraic framework, although originally intended for conventional problem variants, can be extended to cover robust variants. Consequently, this work is mainly concerned with constructing new path algebras that correspond to robust path problems. Such algebras are relatively complex, and they incorporate algebras associated with conventional problems as their building blocks. A benefit of the obtained algebraic formulation is that robust path problems can be solved by well-known general algorithms designed to work over an arbitrary path algebra (e.g. analogues of Gaussian elimination). Indeed, the same algorithms that are used for conventional problems can as well be used for robust problems, although individual algebraic operations within those algorithms are in the robust case more complex. The resulting robust solutions are represented as sets of vectors that are efficient in the Pareto sense.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA