The (Un)Scalability of Heuristic Approximators for NP-Hard Search Problems
This work highlights a scalability issue for researchers and practitioners using machine learning in combinatorial optimization, suggesting it is incremental by questioning recent methods.
The paper tackles the problem of using neural networks to approximate heuristic functions for NP-hard search problems, finding that these approaches do not scale to large instances, with network sizes potentially growing exponentially with instance size.
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.