NEASQC webinar: Hard optimisation problems for smart-charging of electric vehicles

Date: 3 September 2024
Time: 11:00-12:00 CEST

NEASQC is organising a series of interactive webinars to share our findings with the quantum computing community. Each month NEASQC experts present an Open Source library available in the NEASQC GitHub or a technique they investigated, and answer your questions.

In September, we will present some outcomes of the NEASQC use case on Hard optimisation problems for smart-charging of electric vehicles.

The talk will present PhD work done by Margarita Veshchezerova as part of a collaboration between EDF R&D and Université de Lorraine for the upcoming NEASQC deliverable D5.10 “Software suite for benchmarking of quantum algorithms applied to two typical smart-charging optimization problems”:

• Title: Solving a Smart-Charging Special Case as a graph Coloring Problem with a Hybrid Quantum-Classical Decomposition Scheme.
• Authors: (position and institution at the time of the research work): Marc Porcheron (Senior Research Engineer at EDF R&D) and Margarita Veshchezerova (PhD student at EDF R&D and Université de Lorraine, LORIA)

Abstract: In the considered Smart-Charging use case, each electrical vehicle (EV) charge request is given a predefined starting time and processing time, thus defining a time interval. Charges are non-preemptive. The selection of charge requests to be assigned to each charge terminal must satisfy an independence constraint, i.e., the corresponding time intervals must be non-overlapping to each other. In addition the EVs are partitioned in K groups. The Interval Scheduling Problem with group constraints is to select the Maximum Independent Set of time intervals with at most one time interval per group for each terminal. For K>=2 it is NP-hard and there exists no PTAS. For an unrestricted number of terminals, the problem is to minimize the number of terminals to select all time intervals, thus reducing to the graph coloring problem where a color corresponds to a terminal. While the QAOA approach is well suited to search for an MIS,  its recursive variant RQAOA is preferred as it is shown to outperform the classical approach in a significant number of cases. To solve instances of the graph coloring problem, the proposed hybrid scheme is based on conventional Branch&Price (B&P) techniques widely used to solve large integer linear programs. The RQAOA algorithm appearing as a quantum heuristic along with a classical heuristic is integrated as a pricing subproblem in the column generation scheme. Numerical experiments highlight that the quantum-assisted B&P scheme improves the quality of the solutions compared to the B&P scheme for some of the considered instances.

Speaker: Pascale Bendotti, Expert Research Engineer at EDF R&D

Related publications

• Upcoming deliverable D5.10 “Software suite for benchmarking of quantum algorithms applied to two typical smart-charging optimization problems”, which will be available at the end of October 2024 on the use case page. The corresponding open-source code will also be available.