Abstract:

New hardware approaches are emerging, with quantum computers at the forefront, along with other systems such as data-flow machines, mem-computing, and bifurcation chips. All have in common their claim to "solve" challenging, i.e., NP-hard, combinatorial optimization problems more effectively than traditional methods.

NP-hard problems are referred to as "intractable", and, therefore, considered challenging. However, this characterizes the theoretical worst-case complexity for the entire class of problems. The assertion that finding a solution is exceedingly difficult pertains to the decision problem. In contrast, identifying some feasible solution to the optimization version of the problem is often straightforward. For instance, any permutation of cities constitutes a valid tour for the Traveling Salesperson Problem (TSP). The challenge lies in discovering the optimal tour and proving its optimality.

The new approaches primarily can provide "good" solutions but fall short of proving optimality. The theoretical debate extends to whether and to what extent these problems can be approximated in polynomial time. However, the assurance an approximation algorithm offers is merely a lower bound on the solution's quality. Numerous questions remain unanswered, and ultimately, the only method to evaluate the practical performance of heuristic algorithms is to benchmark them against relevant instances. We selected model-independent instances from a diverse set of ten different problem classes where classic exact and heuristic methods are known to have a difficult time. We will present our insights and performance results from classical, quantum, and other new systems.