Conference Agenda

Given an undirected graph, the stable set problem asks to determine the cardinality of the largest subset of pairwise non-adjacent vertices. This value is called the stability number of the graph, and its computation is an NP-hard problem. In our research, we focus on solving the stable set problem using the D-wave quantum annealer. By formulating the problem as a quadratic unconstrained binary optimization problem with the penalty method, we show that the optimal value of this formulation is equal to the stability number of the graph for certain penalty parameter values. However, the D-Wave quantum annealer is not an exact solver, so the solutions may be far from the optimum and may not even represent stable sets. To address this, we introduce a post-processing procedure that identifies samples that could lead to improved solutions and extracts stable sets from them. In addition, we propose a so-called simple CH-partitioning method to handle larger instances that cannot be embedded on D-Wave's quantum processing unit. Finally, we investigate how different penalty parameter values affect the solutions' quality. Extensive computational results show that the post-processing procedure significantly improves the solution quality, while the simple CH-partitioning method successfully extends our approach to medium-size instances.

The Quadratic Unconstrained Binary Optimization (QUBO) problem plays a crucial role in combinatorial optimization and has garnered increased interest with the rise of quantum computing. This talk presents improvements in the state-of-the-art QUBO solver, Qubowl, through refined computational techniques. Our primary focus is on addressing inefficiencies in components of parallel frameworks, notably information loss during node transfers. In our research, we identify several potential drawbacks in the implementation, which we address by carefully evaluating which information should be transferred. This evaluation helps maintain a better trade-off between communication cost and information loss. These enhancements are integrated into the Qubowl solver, which also features a parallel implementation to elevate performance. Comparative empirical evaluations reveal that our enhanced solver achieves improved speed over existing problems, especially in processing sparse QUBO instances.

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 to solve. 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 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.