Abstract
Optimization of pre-production vehicle configurations is one of the challenges in the automotive industry. Given a list of tests requiring cars with certain features, it is desirable to find the minimum number of cars that cover the tests and obey the configuration rules. In this paper, we model the problem in the framework of satisfiability and solve it by utilizing the newly introduced hybrid constrained quadratic model (CQM) solver provided by D-Wave. The problem definition is based on the "Optimizing the Production of Test Vehicles" use case given in the BMW Quantum Computing Challenge. We formulate a constrained quadratic model for the problem and use a greedy algorithm to configure the cars. We benchmark the results obtained from the CQM solver with the results from the classical solvers like CBC (Coin-or branch and cut) and Gurobi. We conclude that the performance of the CQM solver is comparable to classical solvers in optimizing the number of test vehicles. As an extension to the problem, we describe how the scheduling of the tests can be incorporated into the model.
Introduction
In the automotive industry, the production of pre-production "test" vehicles represents a significant capital expenditure. Each vehicle must be meticulously configured with specific features—such as engines, sensors, and trim levels—to satisfy a comprehensive suite of safety and functional tests. However, these configurations are governed by complex "buildability" rules: certain features may be mutually exclusive, while others are mandatory for specific vehicle types.
Mathematically, this challenge is a variant of the Set Cover Problem and Satisfiability (SAT). The objective is to identify the minimum fleet size that satisfies all test requirements while adhering to all engineering constraints. Given the astronomical number of possible configurations, this is an NP-hard optimization problem that becomes increasingly intractable for classical algorithms as the feature set expands.
Problem Formulation and Dataset
The study utilizes a real-world dataset from the BMW Quantum Computing Challenge, specifically focused on the BMW Series 2 Gran Coupe. The dataset comprises:
- 25 features allowed per vehicle type.
- 4,032 specific configuration rules.
- 41 group feature constraints.
- 643 individual test requirements.
To address this, the researchers modeled the problem using two frameworks: Integer Linear Programming (ILP) for classical benchmarking and the Constrained Quadratic Model (CQM) for hybrid quantum-classical solving.
Mathematical Modeling
A critical step in solving this problem is translating the logical "buildability" rules into a format compatible with mathematical solvers. The authors developed a mapping system to convert logical expressions (AND, OR, NOT) into linear equality and inequality constraints.
This mapping allows the use of D-Wave’s hybrid CQM solver, which supports native constraints. Unlike traditional Quadratic Unconstrained Binary Optimization (QUBO) models that require complex penalty coefficient tuning, CQM allows for the direct input of constraints (e.g., $x + y \leq 1$). This significantly lowers the barrier for applying quantum optimization to industrial problems.
The Hybrid Approach and Greedy Strategy
The researchers employed D-Wave’s hybrid CQM solver, which combines classical heuristics with Quantum Processing Unit (QPU) queries to navigate complex search spaces. To manage the solver's 5,000-variable limit, a vehicle-greedy algorithm was implemented. Instead of optimizing the entire fleet simultaneously, the algorithm configures vehicles in "bunches" to cover as many remaining tests as possible, iterating until all requirements are met.
Results and Benchmarking
The hybrid CQM solver was benchmarked against two prominent classical solvers: the open-source CBC (Coin-or branch and cut) and the commercial Gurobi.
| Solver | Fleet Size (Cars) | Runtime (Seconds) |
|---|---|---|
| CBC | 62 | 136.8 |
| Gurobi | 64 | 6.3 |
| D-Wave CQM | 66 | 372.0 |
While classical solvers currently maintain an advantage in both speed and fleet minimization, the CQM solver produced a comparable result of 66 cars. This demonstrates the feasibility of hybrid quantum approaches for high-dimensional, constrained configuration problems.
Key Insights
- Native Constraints: The ability to input constraints directly into the CQM solver is a major advancement over penalty-based QUBO formulations.
- Redundancy Reduction: Simplifying industrial rule sets (e.g., identifying universal rules) was essential for reducing the constraint count and improving solver performance.
- Problem Chunking: The success of the greedy approach suggests that decomposing large-scale industrial problems is a viable strategy for near-term quantum hardware.
Limitations and Future Outlook
The current study highlights several areas for improvement. The 5,000-variable limit necessitated a greedy approach; a global optimization of the entire fleet would likely yield better results but requires higher variable capacity. Additionally, significant runtime overhead is currently attributed to cloud communication and classical pre-processing.
Future work aims to incorporate a "time" dimension for test scheduling. While this exponentially increases the required qubit count, it represents the next step toward a fully integrated industrial optimization tool. As QPU capacity grows, transitioning from greedy "one-car-at-a-time" methods to simultaneous multi-car optimization will be key to closing the performance gap with classical solvers.
Summary updated