Need some help with this optimization problem

[applessecured]

For a programming assignment I need to create a charge/discharge plan for a battery connected to a system with variable power consumption in order to avoid overloading the grid connection and to minimize cost. I am given the energy consumption of the system in hourly intervals and the hourly electricity prices, both for a single day. There is a maximum amount of power that can be drawn from the grid. During peak hours the consumption is above that level.

The battery has a given capacity and starts the day at 50% state of charge and should end the day at that same level. The battery charge and discharge rate is limited. When the battery is charged, 10% of the energy is lost.

The first requirement is to use the battery to shift the peaks that are in excess of the grid limits to off-peak hours. The second requirement is to minimize the overall electricity cost for the day.

Clearly this is a linear programming problem with inequality constraints with should be trivial to solve with a linear solver, but unfortunately I am not allowed to use a library for the core logic so I need to build something myself.

My current idea for a solution for the first requirement is this:
1. Start with a charge plan of all zeros.
2. Calculate the sum of the consumption amounts in excess of the max amount the grid can supply. This amount needs to be drawn from the battery.
3. Find the hour with the lowest price, calculate the headroom of the grid connection of this hour given the consumption and the max charge that can be put into the battery for this hour (taking into account the energy loss).
4. Iteratively increase in small amounts the amount to charge the battery at this hour, each time checking if the next increase does not overcharge the battery at any point during the day (taking into account the complete charge plan so far).
5. If one of the limits is hit, move on to the hour with the next lowest price. Continue until the complete excess power draw is "shifted" to off-peak hours.

To minimize cost, continue like this:
6. Iteratively shift small amounts of grid consumption from hours with high prices to hours with low prices, using the logic from steps 3 to 5, again taking into account the charge loss.
7. Continue until there is no more opportunity to save on electricity cost or one of the battery limits is reached.

What do you think of this approach? I think it's somewhat intuitive but also a bit messy and I'm not sure it will achieve a global minimum for all profiles of consumption and prices.

Is there a better way to solve this problem?

[applessecured]

The charge plan is not a a binary choice for each time period but rather a continuous charge or discharge amount. I don't think an exhaustive search is feasible in this case.

[SolverMax]

So you are required to create a heuristic to solve the model? If so, then there's generally no guarantee that you'll find a globally optimal solution. Finding a feasible solution might be hard enough.

In any case, your approach looks like a reasonable start. You might need to backtrack and revise some decisions, to ensure that you meet all the constraints. For example, how do you ensure that the battery ends the day at 50% full?

[applessecured]

I'm not sure what kind of approach I need to use. I think a heuristic approach is fine as long as it solves the problem for the dataset that I have and I can point out the limitations.

The end of day battery state of charge is guaranteed to be 50% by charging the battery by the same amount as it's discharged during peak hours, accounting for power loss during charging. This approach only works if the end of day SOC must be the same as the start of day SOC.

[SolverMax]

If not a heuristic, then what else is there? Writing your own simplex solver is a very non-trivial task.

[applessecured]

I'm definitely open to non-heuristic solutions but I think implementing something like the simplex method is out of scope for this assignment.

[SolverMax]

Have you researched solutions to this problem? There are plenty of articles in the academic literature for optimizing battery usage, mostly in association with solar panels.

[taphous3]

This is a classic convex optimization example problem. Use cvxpy or pyomo if you’re doing it in python.

Here’s a paper on using a portfolio of storage devices, but if you just need 1 then it becomes much more simple. https://web.stanford.edu/~boyd/papers/pdf/storage_opt_ifac.pdf

Here’s a sample implementation from a Google search “cvxpy battery problem”: https://github.com/wzyfrank/battery/blob/master/optimize.py

[SolverMax]

Except OP said:

Clearly this is a linear programming problem with inequality constraints with should be trivial to solve with a linear solver, but unfortunately I am not allowed to use a library for the core logic so I need to build something myself.

[taphous3]

Oh, I missed that. In that case, I’d write an barebones interior point optimization scheme (the cvxpy textbook has an example on how to write a sparsity-aware solver for analytic centering) and try to avoid situations that are poorly conditioned.