1. |
- Call, Mikael
(author)
-
Shortest Path Routing Modelling, Infeasibility and Polyhedra
- 2012
-
Doctoral thesis (other academic/artistic)abstract
- The Internet is constantly growing but the available resources, i.e. bandwidth, are limited. Using bandwidth efficiently to provide high quality of service to users is referred to as traffic engineering. This is of utmost importance. Traffic in IP networks is commonly routed along shortest paths with respect to auxiliary link weights, e.g. using the OSPF or IS-IS protocol. Here, shortest path routing is indirectly controlled via the link weights only, and it is therefore crucial to have a profound understanding of the shortest path routing mechanism to solve traffic engineering problems in IP networks. The theoretical aspects of such problems have received little attention.Traffic engineering in IP networks leads to very difficult optimization problems and the key element in exact methods for such problems is an inverse shortest path routing problem. It is used to answer the fundamental question of whether there exist link weights that reproduce a set of tentative paths. Path sets that cannot be obtained correspond to routing conflicts. Valid inequalities are instrumental to prohibit such routing conflicts.We analyze the inverse shortest path routing problem thoroughly. We show that the problem is NP-complete, contrary to what is claimed in the literature, and propose a stronger relaxation. Its Farkas system is used to develop a novel and compact formulation based on cycle bases, and to classify and characterize minimal infeasible subsystems. Valid inequalities that prevent routing conflicts are derived and separation algorithms are developed for such inequalities.We also consider several approaches to modelling traffic engineering problems, especially Dantzig–Wolfe reformulations and extended formulations. We give characterizations of facets for some relaxations of traffic engineering problems.Our results contribute to the theoretical understanding, modelling and solution of problems related to traffic engineering in IP networks.
|
|
2. |
- Petropoulos, Fotios, et al.
(author)
-
Operational Research : methods and applications
- 2024
-
In: Journal of the Operational Research Society. - : Taylor & Francis Group. - 0160-5682 .- 1476-9360. ; 75:3, s. 423-617
-
Research review (peer-reviewed)abstract
- Throughout its history, Operational Research has evolved to include methods, models and algorithms that have been applied to a wide range of contexts. This encyclopedic article consists of two main sections: methods and applications. The first summarises the up-to-date knowledge and provides an overview of the state-of-the-art methods and key developments in the various subdomains of the field. The second offers a wide-ranging list of areas where Operational Research has been applied. The article is meant to be read in a nonlinear fashion and used as a point of reference by a diverse pool of readers: academics, researchers, students, and practitioners. The entries within the methods and applications sections are presented in alphabetical order. The authors dedicate this paper to the 2023 Turkey/Syria earthquake victims. We sincerely hope that advances in OR will play a role towards minimising the pain and suffering caused by this and future catastrophes.
|
|