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 -