机组人员配对优化公式的比较研究：为量子计算做准备

量子计算因其在解决具有挑战性的优化问题上潜力巨大而受到广泛讨论。然而，现实世界中的航空公司问题规模目前超出了现有量子硬件的能力。为更大规模的量子硬件做准备需要开发和基准测试最适合量子实现的问题公式。在这项研究中，我们以航空中的机组人员配对问题作为用例，以基准测试不同的问题公式：一个集合划分模型和两个紧凑的公式，即受限流分配问题和可满足性问题（SAT）。对于经典基准测试，我们使用混合整数规划和SAT求解器来解决这些公式。对于量子基准测试，我们将公式转化为二次无约束二进制优化和伊辛公式。我们的基准测试显示，这些问题公式导出了不同的经典和量子特性。在考虑的公式中，SAT公式是未来在量子硬件上实现的最有前途的候选者，它具有最低的非零元素比例和最高的谱间隙，尽管它的线性项系数比例较大。