# Maximize charging, minimize cost

The task pertains to choosing an algorithm based on the data, requirements and constraints.

I have a number of electrical devices ($$d_1,d_2,\dots,d_n$$) with batteries. Throughout the day I will receive these devices with arbitrary battery storage (from 0 to 100%). Batteries have varying capacity. My job is to refill the batteries.

I have to consider the price of charging these devices (cost per unit), since the price of charging a device changes throughout the day, for each day we have 24 different prices for 24 different intervals ($$c_1,c_2,\dots,c_{24}$$).

My goal is to charge these devices optimally, that is determine how much to charge each available device for each time interval in the future, while minimizing the cost of charging them, while also taking into account that I have a limited amount of charging capacity (upper bound) at any one time at $$x$$ units.

Ideally I would like to run this each time I get a new device, to get the current optimal solution. If possible, I would like to avoid having sharp peaks of aggressive charging followed by low (no) charging.

What kind of algorithm can I use for this task? How would I formulate it? Can LP be used for this?

• Can you flesh out some more "If possible, I would like to avoid having sharp peaks of aggressive charging followed by low (no) charging." ? Do you want to impose a penalty for excessive variation in charging, what would that look like, and how it will be traded off (added as penalty?) to raw cost? Or perhaps hard bounds as suggested by @LarrySnyder610 in his comment in response to mine on his answer. Oct 18 '19 at 14:00
• @MarkL.Stone It's not about the difference / range, it's about absolute values. Higher rates of charging are a burden on the system and I will incur penalties because of it. I don't know how I would add this as a penalty, but I would like the charging to be as even as possible over time. Oct 18 '19 at 14:31
• It sounds like you really want (need) a nonlinear cost function to reflect the true cost of higher levels of charging in a period. If this cost can be modeled as piecewise linear, it could be handled by using integer variables; otherwise, an appropriate nonlinear function. I'll leave it to someone else to write out a more detailed answer. cc: @LarrySnyder610 Oct 18 '19 at 14:43