Classical and Quantum Heuristics for the Binary Paint Shop Problem

arXiv:2509.15294v3 Announce Type: replace Abstract: The Binary Paint Shop Problem (BPSP) is an $\mathsf{APX}$-hard optimisation problem arising in automotive manufacturing: given a sequence of $2n$ cars, comprising $n$ distinct models each appearing twice, the task is to decide which of two colours to paint each car so that the two occurrences of each model are painted differently, while minimising consecutive colour swaps. Performance is measured by the paint swap ratio -- the average number of colour changes per car -- which directly affects production efficiency and cost. Prior work showed that the Quantum Approximate Optimisation Algorithm (QAOA) at depth $p=7$ achieves a ratio of $0.393$, outperforming the then-best-known classical heuristic, Recursive Greedy, with a proven asymptotic expected ratio of $0.4$ [Phys. Rev. A 104, 012403 (2021)]. More recently, the Recursive Star Greedy (RSG) heuristic was proposed with a conjectured expected ratio of $0.361$. Here, we formally reduce BPSP to weighted MaxCut, yielding an exact Ising formulation, and benchmark two state-of-the-art low-depth QAOA variants -- eXpressive QAOA and Recursive QAOA -- at $p=1$ (denoted XQAOA$_1$ and RQAOA$_1$) against four classical BPSP heuristics. Across instances ranging from $2^7$ to $2^{12}$ cars, XQAOA$_1$ achieves an average paint-swap ratio of $0.357$; in our instance-wise benchmarks, it outperforms RQAOA$_1$ on almost all instances and each of the four classical baselines, including RSG, on every instance. Surprisingly, RQAOA$_1$ deteriorates with problem size despite employing provably near-optimal QAOA$_1$ parameters at each recursive step, eventually falling behind RSG at the largest sizes. To our knowledge, this is the first report of size-dependent performance degradation of RQAOA$_1$ at scale. In contrast, XQAOA$_1$ remains stable across all tested sizes, with no evidence of size-dependent degradation.

Abstract:The Binary Paint Shop Problem (BPSP) is an $\mathsf{APX}$-hard optimisation problem arising in automotive manufacturing: given a sequence of $2n$ cars, comprising $n$ distinct models each appearing twice, the task is to decide which of two colours to paint each car so that the two occurrences of each model are painted differently, while minimising consecutive colour swaps. Performance is measured by the paint swap ratio -- the average number of colour changes per car -- which directly affects production efficiency and cost. Prior work showed that the Quantum Approximate Optimisation Algorithm (QAOA) at depth $p=7$ achieves a ratio of $0.393$, outperforming the then-best-known classical heuristic, Recursive Greedy, with a proven asymptotic expected ratio of $0.4$ [Phys. Rev. A 104, 012403 (2021)]. More recently, the Recursive Star Greedy (RSG) heuristic was proposed with a conjectured expected ratio of $0.361$. Here, we formally reduce BPSP to weighted MaxCut, yielding an exact Ising formulation, and benchmark two state-of-the-art low-depth QAOA variants -- eXpressive QAOA and Recursive QAOA -- at $p=1$ (denoted XQAOA$_1$ and RQAOA$_1$) against four classical BPSP heuristics. Across instances ranging from $2^7$ to $2^{12}$ cars, XQAOA$_1$ achieves an average paint-swap ratio of $0.357$; in our instance-wise benchmarks, it outperforms RQAOA$_1$ on almost all instances and each of the four classical baselines, including RSG, on every instance. Surprisingly, RQAOA$_1$ deteriorates with problem size despite employing provably near-optimal QAOA$_1$ parameters at each recursive step, eventually falling behind RSG at the largest sizes. To our knowledge, this is the first report of size-dependent performance degradation of RQAOA$_1$ at scale. In contrast, XQAOA$_1$ remains stable across all tested sizes, with no evidence of size-dependent degradation.

32 pages, 3 figures. Final revised version accepted for publication in Physical Review Applied

Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS); Emerging Technologies (cs.ET); Optimization and Control (math.OC)

arXiv:2509.15294 [quant-ph]

(or arXiv:2509.15294v3 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2509.15294 Focus to learn more arXiv-issued DOI via DataCite

https://doi.org/10.1103/dw96-xxfy Focus to learn more DOI(s) linking to related resources

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

analiza aiqbench

Classical and Quantum Heuristics for the Binary Paint Shop Problem

Subiecte conexe