We present a comprehensive case study comparing the performance of D-Waves'
quantum-classical hybrid framework, Fujitsu's quantum-inspired digital
annealer, and Gurobi's state-of-the-art classical solver in solving a transport
robot scheduling problem. This problem originates from an industrially relevant
real-world scenario. We provide three different models for our problem
following different design philosophies. In our benchmark, we focus on the
solution quality and end-to-end runtime of different model and solver
combinations. We find promising results for the digital annealer and some
opportunities for the hybrid quantum annealer in direct comparison with Gurobi.
Our study provides insights into the workflow for solving an
application-oriented optimization problem with different strategies, and can be
useful for evaluating the strengths and weaknesses of different approaches.

我们在一个与行业相关的真实场景中比较了 D-Wave 的量子 - 经典混合框架，Fujitsu 的量子启发式数字退火器和 Gurobi 的最先进的经典求解器在解决智能机器人调度问题时的性能，并通过三种不同的设计哲学为问题提供了三个不同的模型。在我们的基准测试中，我们着重关注不同模型和求解器组合的解决方案质量和端到端运行时间。我们发现了数字退火器的有希望结果，并且与 Gurobi 的直接比较中，混合量子退火器也有一些机会。我们的研究为解决应用导向的优化问题的工作流程提供了洞见，并且对于评估不同方法的优点和缺点非常有用。

一个交通机器人调度问题的量子优化案例研究

A Quantum Optimization Case Study for a Transport Robot Scheduling  Problem

Solving combinatorial optimization (CO) on graphs is among the fundamental
tasks for upper-stream applications in data mining, machine learning and
operations research. Despite the inherent NP-hard challenge for CO, heuristics,
branch-and-bound, learning-based solvers are developed to tackle CO problems as
accurately as possible given limited time budgets. However, a practical metric
for the sensitivity of CO solvers remains largely unexplored. Existing
theoretical metrics require the optimal solution which is infeasible, and the
gradient-based adversarial attack metric from deep learning is not compatible
with non-learning solvers that are usually non-differentiable. In this paper,
we develop the first practically feasible robustness metric for general
combinatorial optimization solvers. We develop a no worse optimal cost
guarantee thus do not require optimal solutions, and we tackle the
non-differentiable challenge by resorting to black-box adversarial attack
methods. Extensive experiments are conducted on 14 unique combinations of
solvers and CO problems, and we demonstrate that the performance of
state-of-the-art solvers like Gurobi can degenerate by over 20% under the given
time limit bound on the hard instances discovered by our robustness metric,
raising concerns about the robustness of combinatorial optimization solvers.

本文提出第一个对组合优化求解器的实用鲁棒性度量方法，并针对 14 个算法和 CO 问题进行了广泛的实验，在给定时间限制下，发现目前的最先进算法（如 Gurobi）在指定的难例上的性能下降了超过 20％，使人们对组合优化求解器的鲁棒性产生担忧。