Scheduling electric vehicle charging in a parking facility is a partition coloring problem. Each vehicle is a partition containing candidate charging intervals. Each interval is a vertex. Conflicts — two vehicles needing the same charger at the same time — are edges. The optimizer must color the graph such that every vehicle gets exactly one interval and no two conflicting intervals share a color.
The classical approach uses branch-and-price, where a restricted master problem selects combinations of feasible intervals and a pricing subproblem finds new columns by solving a maximum independent set problem. Gurobi handles both. It works well on small instances.
The quantum-classical hybrid replaces the pricing subproblem with quantum-annealing-inspired algorithms. The maximum independent set problem is reformulated as a QUBO and solved via simulated coherent Ising machines. On small and medium instances, the hybrid matches pure Gurobi. On large and hard instances, it clearly outperforms — closing optimality gaps that Gurobi couldn't resolve within the same time budget.
The insight is structural. Quantum advantage doesn't appear in the master problem, which has nice linear structure that Gurobi handles efficiently. It appears in the subproblem, which is NP-hard and combinatorial — exactly the landscape where quantum annealing's ability to tunnel through energy barriers gives it an edge. The hybrid doesn't replace classical optimization. It surgically augments the part that was bottlenecking.
Knowing where the hard part is determines where to deploy the expensive tool.