8
$\begingroup$

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?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark L. Stone Oct 18 '19 at 14:00
  • $\begingroup$ @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. $\endgroup$ – user2974951 Oct 18 '19 at 14:31
  • $\begingroup$ 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 $\endgroup$ – Mark L. Stone Oct 18 '19 at 14:43
3
$\begingroup$

I would encourage you to think about the model and the algorithm separately. I think your question is really about what sort of model you should build. Once you know that, the question of algorithm is largely determined, because you'll probably just be passing your model to a solver that will handle the algorithmic part automatically.

My short answer is that it sounds like your problem can be modeled as an LP. There don't seem to be any nonlinearities (which would arise if, say, the charging cost was a nonlinear function of the amount of energy charged) or binary variables (which would arise if, say, there was a fixed cost to start charging a battery).

So, I would recommend formulating this as an LP. If you get stuck while you're doing that, folks here can help. Once you have formulated the model, you'll want to implement it in a modeling language and then send it to an LP solver. This Q&A might help get you started on that part.

Assuming the problem isn't too huge (thousands and thousands of batteries or time periods, for example), it should solve quickly in an LP solver, and I would guess that you'll be able to solve it every time you get a new device.

Improve this answer
$\endgroup$
  • $\begingroup$ OP still needs to think about how to handle " If possible, I would like to avoid having sharp peaks of aggressive charging followed by low (no) charging.". Would some nonlinearity (quadratic?) be used for that? $\endgroup$ – Mark L. Stone Oct 18 '19 at 13:57
  • 1
    $\begingroup$ I'd say there are various ways to handle this. One way is to put a bound on max charge in one period, or on the gap between max and min charge, or something like that -- those would be linear. Could also use a nonlinear term as you suggested. In either case, it's likely to hurt the solve time somewhat. $\endgroup$ – LarrySnyder610♦ Oct 18 '19 at 13:59
  • $\begingroup$ @LarrySnyder610 Yes, I am asking about the model and it's specification. I will be using software to do all the hard work. I am interested in the actual model definition, the maximization / minimization function. How would I go about that for my problem specifically? $\endgroup$ – user2974951 Oct 18 '19 at 15:33
  • $\begingroup$ As @LarrySnyder610 said, one way to formulate this problem is MILP. Once, I saw such a problem which had been formulated as VRP variant (E.g. Electric Vehicle Routing Problem). This may not be exactly what you are looking for but, I hope it will be useful. $\endgroup$ – A.Omidi Oct 18 '19 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.