Algorithms for Nonconvex EV Charging Problems

Due to the fast increasing number of electric vehicles (EVs) and the resulting stress on the electricity grid, smart charging algorithms are needed to prevent grid problems. EV charging problems have already been topic of research before, but the focus was mainly on convex objective functions. For nonconvex objectives, however, there is no efficient solution method available. However, such objectives occur when e.g. charging efficiency is taken into account. We show that this addition makes the problem NP-hard in general but a polynomial time algorithm still exists when the objective function is concave. Furthermore, an approximation algorithm is given with a performance that is bounded by the maximum difference between the given objective function and its convex envelope. Finally, we show how this algorithm can be applied to the EV charging problem.