Standard

A Problem-Specific Branch-and-Bound Algorithm for the Protected Shortest Simple Path Problem with Must-Pass Nodes. / Ogorodnikov, Yuri; Rudakov, Roman; Khachai, Daniil et al.
In: IFAC-PapersOnLine, Vol. 55, No. 10, 01.01.2022, p. 572-577.

Research output: Contribution to journal › Article › peer-review

Harvard

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, vol. 55, no. 10, pp. 572-577. https://doi.org/10.1016/j.ifacol.2022.09.455

APA

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

Vancouver

Ogorodnikov Y, Rudakov R, Khachai D, Khachay M. A Problem-Specific Branch-and-Bound Algorithm for the Protected Shortest Simple Path Problem with Must-Pass Nodes. IFAC-PapersOnLine. 2022 Jan 1;55(10):572-577. doi: 10.1016/j.ifacol.2022.09.455

Author

Ogorodnikov, Yuri ; Rudakov, Roman ; Khachai, Daniil et al. / A Problem-Specific Branch-and-Bound Algorithm for the Protected Shortest Simple Path Problem with Must-Pass Nodes. In: IFAC-PapersOnLine. 2022 ; Vol. 55, No. 10. pp. 572-577.

BibTeX

@article{864d840ff1d34f8fbdc28d833db7164c,
title = "A Problem-Specific Branch-and-Bound Algorithm for the Protected Shortest Simple Path Problem with Must-Pass Nodes",
abstract = "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 {\textquoteright}Rome99{\textquoteright} 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.",
author = "Yuri Ogorodnikov and Roman Rudakov and Daniil Khachai and Michael Khachay",
note = "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).",
year = "2022",
month = jan,
day = "1",
doi = "10.1016/j.ifacol.2022.09.455",
language = "English",
volume = "55",
pages = "572--577",
journal = "IFAC-PapersOnLine",
issn = "2405-8963",
publisher = "Elsevier BV",
number = "10",

}

RIS

TY - JOUR

T1 - A Problem-Specific Branch-and-Bound Algorithm for the Protected Shortest Simple Path Problem with Must-Pass Nodes

AU - Ogorodnikov, Yuri

AU - Rudakov, Roman

AU - Khachai, Daniil

AU - Khachay, Michael

N1 - 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).

PY - 2022/1/1

Y1 - 2022/1/1

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

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

UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=000881681700097

UR - http://www.scopus.com/inward/record.url?partnerID=8YFLogxK&scp=85144491168

U2 - 10.1016/j.ifacol.2022.09.455

DO - 10.1016/j.ifacol.2022.09.455

M3 - Article

VL - 55

SP - 572

EP - 577

JO - IFAC-PapersOnLine

JF - IFAC-PapersOnLine

SN - 2405-8963

IS - 10

ER -

ID: 32804553