Accelerating TSP approximation through problem encoding optimization
In the first project phase we developed an algorithm that partitions instances of combinatorial optimization problems into several small subinstances of the same size. Selectively solving some of these subproblems and combining their solutions yields a solution for the original problem statement. This approach was motivated by the limited qubit count of currently available quantum hardware. In the follow-up project we concerned ourselves with the method of solving said generated subproblems. In the first project we implemented QAOA to solve subproblems as described in research papers. However, we noticed shortcomings in runtime and solution quality, severely affecting the overall result. Hence, we decided to construct a different problem encoding for the TSP that would allow us to implement the problem parameters and constraints more directly in a quantum circuit. The core idea is to encode the distances between points directly instead of a 1-hot encoded point sequence. We present our implementation and results in the demonstrator and contrast it with the previous approach.
Scenario-based route planning to safeguard automotive driving functions (TSP/ORP)
The demonstrator shows two different modeling approaches and corresponding implementation for scenario-based route planning. The first approach is based on a QAOA implementation created as part of the project for the "Traveling Salesperson Problem". In addition, an algorithm for partitioning the TSP developed in the course of the project will be demonstrated. The algorithm, which is based on A*, splits large TSP instances into several smaller ones so that they can be solved on the quantum computer. This approach is hybrid, whereby the partitioning takes place on a classical computer and only the difficult combinatorial »core« of the problem is solved on a quantum computer. Our QAOA implementation is embedded into this algorithm and can alternatively be exchanged with classical solver for comparison. In order to guide the choices of our method on which subinstanced to generate, several heuristics have been developed. This includes notably a small neural network that can estimate the expected length of a TSP instance. The second approach models the problem as an orienteering problem rather than the usual TSP. The orienteering problem is a combination of TSP and knapsack problem. In this approach, we show how this different kind of modeling affects the implementation and the complexity of the underlying optimization problem.
Disclaimer
The interactive demonstrator notebooks have been licensed under the Apache licence (version 2.0). The files may only be used in accordance with the licence. A copy of the licence can be downloaded from http://www.apache.org/licenses/LICENSE-2.0 Except as required by applicable law or agreed to in writing, software distributed under this licence is distributed on an "AS IS" basis, without warranties or conditions of any kind, either express or implied. See the licence for the specific rights and restrictions associated with it.
This is a research prototype. Liability for loss of profit, loss of production, business interruption, loss of use, loss of data and information, financing costs and other financial and consequential damage is excluded, except in cases of gross negligence, intent and personal injury.