Enhanced Methods for the Weight Constrained Shortest Path Problem

• URL: http://arxiv.org/abs/2207.14744v2
• Date: Fri, 30 Jun 2023 04:25:12 GMT
• Title: Enhanced Methods for the Weight Constrained Shortest Path Problem
• Authors: Saman Ahmadi, Guido Tack, Daniel Harabor, Philip Kilby, Mahdi Jalili
• Abstract summary: The Weight Constrained Shortest Path Problem (WCSPP) is a well-studied, yet challenging, topic in AI. This paper presents two new solution approaches to the WCSPP on the basis of A* search. We empirically evaluate the performance of our algorithms on a set of large and realistic problem instances.
• Score: 18.567812400186092
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The classic problem of constrained pathfinding is a well-studied, yet challenging, topic in AI with a broad range of applications in various areas such as communication and transportation. The Weight Constrained Shortest Path Problem (WCSPP), the base form of constrained pathfinding with only one side constraint, aims to plan a cost-optimum path with limited weight/resource usage. Given the bi-criteria nature of the problem (i.e., dealing with the cost and weight of paths), methods addressing the WCSPP have some common properties with bi-objective search. This paper leverages the recent state-of-the-art techniques in both constrained pathfinding and bi-objective search and presents two new solution approaches to the WCSPP on the basis of A* search, both capable of solving hard WCSPP instances on very large graphs. We empirically evaluate the performance of our algorithms on a set of large and realistic problem instances and show their advantages over the state-of-the-art algorithms in both time and space metrics. This paper also investigates the importance of priority queues in constrained search with A*. We show with extensive experiments on both realistic and randomised graphs how bucket-based queues without tie-breaking can effectively improve the algorithmic performance of exhaustive A*-based bi-criteria searches.

Related papers

• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• Optimizing Tensor Contraction Paths: A Greedy Algorithm Approach With Improved Cost Functions [1.3812010983144802]
  We introduce a novel approach based on the greedy algorithm by opt_einsum that computes efficient contraction paths in less time. With our approach, we are even able to compute paths for large problems where modern algorithms fail.
  arXiv  Detail & Related papers  (2024-05-08T09:25:39Z)
• BalMCTS: Balancing Objective Function and Search Nodes in MCTS for Constraint Optimization Problems [7.196057722218442]
  Constraint Problems Optimization (COP) pose intricate challenges in problems usually addressed through Branch and Bound (B&B) methods. We propose a novel neural network algorithm based on a depth-first search algorithm for solving COP. Our method identifies feasible solutions with a gap of less than 17.63% within the initial 5 feasible solutions.
  arXiv  Detail & Related papers  (2023-12-26T03:09:08Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Tightest Admissible Shortest Path [4.928034044959278]
  shortest path problem in graphs is fundamental to AI. We introduce the problem of finding the admissible shortest path (TASP), a path with the tightest suboptimality bound on the optimal cost. We present a complete algorithm for solving TASP, with guarantees on solution quality.
  arXiv  Detail & Related papers  (2023-08-15T14:39:05Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  The critical node problem (CNP) aims to find a set of critical nodes from a network whose deletion maximally degrades the pairwise connectivity of the residual network. This work proposes a feature importance-aware graph attention network for node representation. It combines it with dueling double deep Q-network to create an end-to-end algorithm to solve CNP for the first time.
  arXiv  Detail & Related papers  (2021-12-03T14:23:05Z)
• Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds [5.158632635415881]
  State-of-the-art approach to computing optimal solutions is Conflict-Based Search (CBS) We revisit the complexity analysis of CBS to provide tighter bounds on the algorithm's run-time in the worst-case.
  arXiv  Detail & Related papers  (2021-04-18T07:46:28Z)
• Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles [1.370633147306388]
  Path finding is a well-studied problem in AI, which is often framed as graph search. We present two algorithms, grounded in the same idea, that can obtain provably optimal solutions to the considered problem.
  arXiv  Detail & Related papers  (2021-04-14T07:59:53Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.