A Problem-Specific Branch-and-Bound Algorithm for the Protected Shortest Simple Path Problem with Must-Pass Nodes
Электронный научный архив УРФУ
Информация об архиве | Просмотр оригинала| Поле | Значение | |
| Заглавие |
A Problem-Specific Branch-and-Bound Algorithm for the Protected Shortest Simple Path Problem with Must-Pass Nodes
|
|
| Автор |
Ogorodnikov, Y.
Rudakov, R. Khachai, D. Khachay, M. |
|
| Тематика |
BRANCH-AND-BOUND ALGORITHM
MILP MODELS PROTECTED SHORTEST SIMPLE PATH PROBLEM WITH MUST-PASS NODES BRANCH AND BOUND METHOD GRAPH ALGORITHMS INTEGER PROGRAMMING BRANCH-AND-BOUND ALGORITHMS FIXED SIZE MILP MODEL PATH PROBLEMS PROTECTED SHORT SIMPLE PATH PROBLEM WITH MUST-PASS NODE SIMPLE++ STRONGLY NP-HARD TRANSPORTATION COST VERTEX DISJOINT PATHS WEIGHTED DIRECTED GRAPH DIRECTED GRAPHS |
|
| Описание |
An instance of the Protected Shortest Simple Path Problem with Must-Pass Nodes (PSSPP-MPN) is specified by an edge-weighted directed graph with dedicated source, destination, and additional must-pass nodes. The goal is to find two vertex-disjoint paths, such that the former one is simple, visits all the must-pass nodes, and has the minimum transportation cost. In this paper, we show that the PSSPP-MPN is strongly NP-hard even for subsets of must-pass nodes of arbitrary fixed size and propose a novel problem-specific branch-and-bound algorithm for this problem. Results of competitive numerical evaluation against the public dataset'Rome99' from the 9th DIMACS Implementation Challenge show that the proposed algorithm notably outperforms the state-of-the-art MIP-optimizer Gurobi both by accuracy and execution time. © 2022 The Authors. This is an open access article under the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0/)
Ural Mathematical Center Ministry of Education and Science of the Russian Federation, Minobrnauka, (075-02-2022-874) Yuri Ogorodnikovfl Roman Rudakovfl and Michael Khachay were supported by Ural Mathematical Center and the Ministry of Science and Higher Education of the Russian Federation (Agreement no. 075-02-2022-874). |
|
| Дата |
2024-04-22T15:52:58Z
2024-04-22T15:52:58Z 2022 |
|
| Тип |
Conference paper
Conference object (info:eu-repo/semantics/conferenceObject) Published version (info:eu-repo/semantics/publishedVersion) |
|
| Идентификатор |
Ogorodnikov, Y, Rudakov, R, Khachai, D & Khachay, M 2022, 'A Problem-Specific Branch-and-Bound Algorithm for the Protected Shortest Simple Path Problem with Must-Pass Nodes', IFAC-PapersOnLine, Том. 55, № 10, стр. 572-577. https://doi.org/10.1016/j.ifacol.2022.09.455
Ogorodnikov, Y., Rudakov, R., Khachai, D., & Khachay, M. (2022). A Problem-Specific Branch-and-Bound Algorithm for the Protected Shortest Simple Path Problem with Must-Pass Nodes. IFAC-PapersOnLine, 55(10), 572-577. https://doi.org/10.1016/j.ifacol.2022.09.455 2405-8963 Final All Open Access; Bronze Open Access https://doi.org/10.1016/j.ifacol.2022.09.455 https://doi.org/10.1016/j.ifacol.2022.09.455 http://elar.urfu.ru/handle/10995/132375 10.1016/j.ifacol.2022.09.455 85144491168 881681700097 |
|
| Язык |
en
|
|
| Права |
Open access (info:eu-repo/semantics/openAccess)
|
|
| Формат |
application/pdf
|
|
| Издатель |
Elsevier B.V.
|
|
| Источник |
IFAC-PapersOnLine
IFAC-PapersOnLine |
|