The (Un)Scalability of Heuristic Approximators for NP-Hard Search Problems
The A* algorithm is commonly used to solve NP-hard combinatorial optimization problems. When provided with a completely informed heuristic function, A* solves many NP-hard minimum-cost path problems in time polynomial in the branching factor and the number of edges in a minimum-cost path. Thus, approximating their completely informed heuristic functions with high precision is NP-hard. We therefore examine recent publications that propose the use of neural networks for this purpose. We support our claim that these approaches do not scale to large instance sizes both theoretically and experimentally. Our first experimental results for three representative NP-hard minimum-cost path problems suggest that using neural networks to approximate completely informed heuristic functions with high precision might result in network sizes that scale exponentially in the instance sizes. The research community might thus benefit from investigating other ways of integrating heuristic search with machine learning.
Code (1)
Tasks
Combinatorial OptimizationHeuristic SearchSimilar Papers 제목 키워드 기반
HSVI for zs-POSGs using Concavity, Convexity and Lipschitz Properties
Dynamic programming and heuristic search are at the core of state-of-the-art solvers for sequential decision-making problems. In partially observable or collaborative settings (\eg, POMDPs and Dec-POMDPs), this requires …
Decision MakingHeuristic SearchSequential Decision MakingFast Continuous and Integer L-shaped Heuristics Through Supervised Learning
We propose a methodology at the nexus of operations research and machine learning (ML) leveraging generic approximators available from ML to accelerate the solution of mixed-integer linear two-stage stochastic programs. …
ManagementA* Search Without Expansions: Learning Heuristic Functions with Deep Q-Networks
Efficiently solving problems with large action spaces using A* search has been of importance to the artificial intelligence community for decades. This is because the computation and memory requirements of A* search grow…
Rubik's CubeEnhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update
Combinatorial optimization (CO) problems are crucial in various scientific and industrial applications. Recently, researchers have proposed using unsupervised Graph Neural Networks (GNNs) to address NP-hard combinatorial…
Combinatorial OptimizationComputational EfficiencyNature Inspired Metaheuristic Effectiveness Used in Phishing Intrusion Detection Systems with Grey Wolf Algorithm Techniques
This paper discusses research-based findings of applying metaheuristic optimization techniques and nature-inspired algorithms to detect and mitigate phishing attacks. The focus will be on the Grey Wolf nature-inspired me…
Intrusion DetectionMetaheuristic Optimization