Frauke Liers

Kevin-Martin Aigner, Marc Goerigk, Michael Hartisch et al.

Advancements in mathematical programming have made it possible to efficiently tackle large-scale real-world problems that were deemed intractable just a few decades ago. However, provably optimal solutions may not be accepted due to the perception of optimization software as a black box. Although well understood by scientists, this lacks easy accessibility for practitioners. Hence, we advocate for introducing the explainability of a solution as another evaluation criterion, next to its objective value, which enables us to find trade-off solutions between these two criteria. Explainability is attained by comparing against (not necessarily optimal) solutions that were implemented in similar situations in the past. Thus, solutions are preferred that exhibit similar features. Although we prove that already in simple cases the explainable model is NP-hard, we characterize relevant polynomially solvable cases such as the explainable shortest path problem. Our numerical experiments on both artificial as well as real-world road networks show the resulting Pareto front. It turns out that the cost of enforcing explainability can be very small.

Friedrich Wagner, Frauke Liers

Motivated by recent progress in quantum hardware and algorithms researchers have developed quantum heuristics for optimization problems, aiming for advantages over classical methods. To date, quantum hardware is still error-prone and limited in size such that quantum heuristics cannot be scaled to relevant problem sizes and are often outperformed by their classical counterparts. Moreover, if provably optimal solutions are desired, one has to resort to classical exact methods. As however quantum technologies may improve considerably in future, we demonstrate in this work how quantum heuristics with limited resources can be integrated in large-scale exact optimization algorithms for NP-hard problems. To this end, we consider vehicle routing as prototypical NP-hard problem. We model the pricing and separation subproblems arising in a branch-price-and-cut algorithm as quadratic unconstrained binary optimization problems. This allows to use established quantum heuristics like quantum annealing or the quantum approximate optimization algorithm for their solution. A key feature of our algorithm is that it profits not only from the best solution returned by the quantum heuristic but from all solutions below a certain cost threshold, thereby exploiting the inherent randomness is quantum algorithms. Moreover, we reduce the requirements on quantum hardware since the subproblems, which are solved via quantum heuristics, are smaller than the original problem. We provide an experimental study comparing quantum annealing to simulated annealing and to established classical algorithms in our framework. While our hybrid quantum-classical approach is still outperformed by purely classical methods, our results reveal that both pricing and separation may be well suited for quantum heuristics if quantum hardware improves.

Anuraag Mishra, Andrea Gilch, Benjamin Apeleo Zubiri et al.

In this work, we develop a novel technique for reconstructing images from projection-based nano- and microtomography. Our contribution focuses on enhancing reconstruction quality, particularly for specimen composed of homogeneous material phases connected by sharp edges. This is accomplished by training a neural network to identify edges within subpictures. The trained network is then integrated into a mathematical optimization model, to reduce artifacts from previous reconstructions. To this end, the optimization approach favors solutions according to the learned predictions, however may also determine alternative solutions if these are strongly supported by the raw data. Hence, our technique successfully incorporates knowledge about the homogeneity and presence of sharp edges in the sample and thereby eliminates blurriness. Our results on experimental datasets show significant enhancements in interface sharpness and material homogeneity compared to benchmark algorithms. Thus, our technique produces high-quality reconstructions, showcasing its potential for advancing tomographic imaging techniques.