26th Australian Institute of Physics Congress and the Australian and New Zealand Conference on Optics and Photonics

Classical and Quantum Heuristics for the Binary Paint Shop Problem

Not scheduled

20m

Belinda Hutchinson Building (The University of Sydney )

Poster ANZOS | Quantum Computing and Quantum Information (ANZCOP QCQI)

Description

The Binary Paint Shop Problem (BPSP) is a well-known $\mathsf{APX}$-hard optimisation problem with important applications in automotive manufacturing. Given a sequence of $2n$ cars, where each of $n$ car types appears exactly twice, the goal is to assign two colours so that each car type receives both colours while minimising consecutive colour changes. Performance is measured by the paint swap ratio, the average number of colour changes per car, with lower ratios improving production efficiency and reducing material waste.

Recently, Streif et al. showed that the Quantum Approximate Optimisation Algorithm at $p=7$ (QAOA$_7$) achieves an expected paint swap ratio of $0.393$, outperforming the classical Recursive Greedy (RG) heuristic ratio of $0.4$. A newer classical heuristic, Recursive Star Greedy (RSG), was further conjectured to achieve a ratio of $0.361$. In this work, we investigate two state-of-the-art QAOA variants, eXpressive QAOA (XQAOA) and Recursive QAOA (RQAOA), and compare them against the best known classical heuristics.

We first introduce a rigorous reduction from BPSP instances with $2n$ cars to a graph-colouring problem on $n$ vertices, which we call the Initial-Car-Colour (ICC) encoding. This encoding provides a new structural perspective on the problem while reducing the Hamiltonian size by a factor of two. Benchmarking XQAOA$_1$ and RQAOA$_1$ on instances with $N=2^7$ to $2^{12}$ cars, we find that XQAOA$_1$ achieves an average paint swap ratio of $0.357$, consistently outperforming RQAOA$_1$ and classical heuristics across nearly all instances. Contrary to the conjectured RSG ratio of $0.361$, our empirical results suggest its true average ratio is closer to $0.371$.

Notably, RQAOA$_1$ exhibits performance degradation with increasing problem size, despite using provably optimal QAOA$_1$ parameters at each recursive step. To our knowledge, this is the first work to identify this large-scale degradation. In contrast, XQAOA$_1$ maintains robust performance, suggesting strong potential as a quantum heuristic for the BPSP.