2195. Neighbourhood-constrained Bilevel Shortest Path Problem
Invited abstract in session WC-2: Bilevel Optimization, stream Discrete and Combinatorial Optimization.
Wednesday, 13:30-15:00Room: H4
Authors (first author is the speaker)
| 1. | Szymon Wróbel
|
| Department of Fundamentals of Computer Science, Wrocław University of Science and Technology | |
| 2. | Adam Kasperski
|
| Wroclaw University of Science and Technology, Faculty of Management | |
| 3. | Pawel Zielinski
|
| Department of Fundamentals of Computer Science, Wroclaw University of Science and Technology |
Abstract
The Shortest Path problem is one of the classical combinatorial optimisation problems that has been extensively studied in the deterministic setting, where the arc weights are precisely known. While this model is often sufficient, real-world applications frequently involve uncertainty, limited control over input data, or a partitioning of decision variables among multiple decision makers. One of the approaches suitable in that setting is bilevel optimisation -- a framework in which the problem is divided into two hierarchically dependent subproblems.
In this work, we introduce a new problem: the Neighbourhood-Constrained Bilevel Shortest Path Problem (NCBSP), where the follower's decision space is restricted to the neighbourhood of the leader's decision. We present preliminary results on the computational complexity of the NCBSP and explore its relationships to other well-known optimisation problems.
Keywords
- Graphs and Networks
- Mathematical Programming
Status: accepted
Back to the list of papers