Glasnik Matematicki, Vol. 55, No. 1 (2020), 143-176.

AN ALGEBRAIC FRAMEWORK FOR MULTI-OBJECTIVE AND ROBUST VARIANTS OF PATH PROBLEMS

Robert Manger

Department of Mathematics, Faculty of Science, University of Zagreb, Bijenička cesta 30, 10 000 Zagreb, Croatia
e-mail: manger@math.hr

Abstract.   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.

2010 Mathematics Subject Classification.   90C35, 90C29, 05C38, 16Y60, 68R10

Key words and phrases.   Directed graphs, path problems, path algebras, multi-objective optimization, robust optimization, Pareto efficiency, min-max (regret)

https://doi.org/10.3336/gm.55.1.12

References:

1. H. Aissi, C. Bazgan and D. Vanderpooten, Min-max and min-max regret versions of combinatorial optimization problems: A survey, European J. Oper. Res. 197 (2009), 427-438.
   MathSciNet     CrossRef

2. R. Backhouse, Regular algebra applied to language problems, J. Log. Algebr. Program. 66 (2006), 71-111.
   MathSciNet     CrossRef

3. J.S. Baras and G. Theodorakopoulos, Path problems in networks, Synthesis Lectures on Communication Networks, Morgan & Claypool Publishers, San Rafael CA, 2010.

4. D. Bertsimas, D.B. Brown and C. Caramanis, Theory and applications of robust optimization, SIAM Rev. 53 (2011), 464-501.
   MathSciNet     CrossRef

5. B. Carré, Graphs and networks, Oxford University Press, Oxford, 1979.
   MathSciNet    

6. P. de la Torre and C.P. Kruskal, Fast parallel algorithms for all-sources lexicographic search and path-algebra problems, J. Algorithms 19 (1995), 1-24.
   MathSciNet     CrossRef

7. C.T. Djamégni, P. Quinton, S. Rajopadhye and T. Risset, Derivation of systolic algorithms for the algebraic path problem by recurrence transformations, Parallel Comput. 26 (2000), 1429-1445.
   CrossRef

8. M. Ehrgott, Multicritera optimization, 2nd Edition, Springer, Berlin, 2010.

9. J.S. Golan, Semirings and their applications, Kluwer Academic Publishers, Dortrecht, 1999.
   MathSciNet     CrossRef

10. M. Gondran and M. Minoux, Graphs, dioids and semirings. New models and algorithms, Springer, Berlin, 2008.
    MathSciNet    

11. A.J.T. Gurney and T.G. Griffin, Lexicographic products in metarouting, in: Proceedings of the International Conference on Network Protocols (ICNP), Beijing, China, October 16-19, 2007, (eds. K.L. Calvert and D. Yau), IEEE Computer Society, Piscataway NJ, 2007, 113-122.

12. T.G. Griffin, Exploring the stratisfied shortest-paths problem, Netw. Sci. 1 (2012), 2-14.

13. U. Huckenbeck, Extremal paths in graphs, Akademie Verlag, Berlin, 1997.
    MathSciNet    

14. D. Jungnickel, Graphs, networks and algorithms, Fourth Edition, Springer, Berlin, 2013.
    MathSciNet     CrossRef

15. A. Kasperski and P. Zielinski, Robust discrete optimization under discrete and interval uncertainty: A survey, in: Robustness Analysis in Decision Aiding, Optimization, and Analytics (eds. M, Doumpos, C. Zopounidis and E. Grigoroudis), Springer, Cham CH, 2016, 113-143.
    MathSciNet    

16. V.N. Kolokoltsov, Idempotent structures in optimization, Journal of Mathematical Sciences 104 (2001), 847-880.
    MathSciNet    

17. P. Kouvelis and G. Yu, Robust discrete optimization and its applications, Springer, Berlin, 1997.
    MathSciNet     CrossRef

18. J-Y. Le Boudec and P. Thiran, Network calculus. A theory of deterministic queuing systems for the internet, Lecture Notes in Computer Science 2050, Springer, Berlin, Online Version April 26, 2012.
    MathSciNet     CrossRef

19. F.S. Lobato and V. Steffen Jr., Multi-objective optimization problems: concepts and self-adaptive parameters with mathematical and engineering applications, Springer, Cham, 2017.
    MathSciNet     CrossRef

20. R. Manger, Gaussian block algorithms for solving path problems, Math. Commun. 3 (1998), 67-81.
    MathSciNet    

21. R. Manger, Solving path problems on a network of computers, Informatica (Ljubl.) 26 (2002) 91-100.
    MathSciNet    

22. R. Manger, A new path algebra for finding paths in graphs, in: Proceedings of the 26th International Conference on Information Technology Interfaces - ITI 2004, Cavtat, Croatia, June 7-10, 2004. (eds. V. Lužar-Stiffler, and V. Hljuz Dobrić), University Computing Centre, Zagreb, 2004, 657-662.

23. R. Manger, Composite path algebras for solving path problems in graphs, Ars Combin. 78 (2006), 137-150.
    MathSciNet    

24. M. Mohri, Semiring frameworks and algorithms for shortest-distance problems, J. Autom. Lang. Comb. 7 (2002), 321-350.
    MathSciNet    

25. G. Rote, Path problems in graphs, Comput. Suppl. 7 (1990), 155-189.
    MathSciNet     CrossRef

26. M. Russling, Deriving a class of layer-oriented graph algorithms, Sci. Comput. Programming 26 (1996), 117-132.
    MathSciNet     CrossRef

27. K.K. Somasundaram and J.S. Baras, Solving multi-metric network problems: An interplay between idempotent semiring rules, Linear Algebra Appl. 435 (2011), 1494-1512.
    MathSciNet     CrossRef

28. A. Wongseelashote, Semirings and path spaces, Discrete Math. 26 (1979), 55-78.
    MathSciNet     CrossRef