hrcak mascot   Srce   HID

Original scientific paper
https://doi.org/10.3336/gm.55.1.12

An algebraic framework for multi-objective and robust variants of path problems

Robert Manger   ORCID icon orcid.org/0000-0003-0953-6517 ; Department of Mathematics, Faculty of Science, University of Zagreb, Bijenička cesta 30, 10 000 Zagreb, Croatia

Fulltext: english, pdf (316 KB) pages 143-176 downloads: 152* cite
APA 6th Edition
Manger, R. (2020). An algebraic framework for multi-objective and robust variants of path problems. Glasnik matematički, 55 (1), 143-176. https://doi.org/10.3336/gm.55.1.12
MLA 8th Edition
Manger, Robert. "An algebraic framework for multi-objective and robust variants of path problems." Glasnik matematički, vol. 55, no. 1, 2020, pp. 143-176. https://doi.org/10.3336/gm.55.1.12. Accessed 25 Oct. 2021.
Chicago 17th Edition
Manger, Robert. "An algebraic framework for multi-objective and robust variants of path problems." Glasnik matematički 55, no. 1 (2020): 143-176. https://doi.org/10.3336/gm.55.1.12
Harvard
Manger, R. (2020). 'An algebraic framework for multi-objective and robust variants of path problems', Glasnik matematički, 55(1), pp. 143-176. https://doi.org/10.3336/gm.55.1.12
Vancouver
Manger R. An algebraic framework for multi-objective and robust variants of path problems. Glasnik matematički [Internet]. 2020 [cited 2021 October 25];55(1):143-176. https://doi.org/10.3336/gm.55.1.12
IEEE
R. Manger, "An algebraic framework for multi-objective and robust variants of path problems", Glasnik matematički, vol.55, no. 1, pp. 143-176, 2020. [Online]. https://doi.org/10.3336/gm.55.1.12

Abstracts
It is well known that various types of path problems in graphs can be treated together within a common algebraic framework. Thereby each type is characterized by a different ``path algebra", i.e., a different instance of the same abstract algebraic structure. This paper demonstrates that the common algebraic framework, although originally intended for conventional problem variants, can be extended to cover multi-objective and robust variants. Thus the paper is mainly concerned with constructing and justifying new path algebras that correspond to such more complex problem varieties. A consequence of the obtained algebraic formulation is that multi-objective or robust problem instances can be solved by well-known general algorithms designed to work over an arbitrary path algebra. The solutions obtained in this way comprise all paths that are efficient in the Pareto sense. The efficient paths are by default described only implicitly, as vectors of objective-function values. Still, it is shown in the paper that, with slightly extended versions of the involved algebras, the same paths can also be identified explicitly. Also, for robust problem instances it is possible to select only one ``robustly optimal" path according to a generalized min-max or min-max regret criterion.

Keywords
Directed graphs; path problems; path algebras; multi-objective optimization; robust optimization; Pareto efficiency; min-max (regret)

Hrčak ID: 239054

URI
https://hrcak.srce.hr/239054

Visits: 312 *