The Math Trick That Makes Battery Scheduling 100x Faster

The Algorithm That Saves Batteries From Impossible Decisions

Imagine you're managing a massive battery storage system — the kind that keeps hospitals running during blackouts, buffers renewable energy when the sun isn't shining, and keeps the lights on when demand spikes. Every fifteen minutes, you face a decision: charge the battery (buy energy cheap) or discharge it (sell energy dear). You cannot do both simultaneously. That's not a preference — it's physics. A battery cannot be charging and discharging at the exact same moment.

Yet for decades, the mathematical tools engineers use to plan these decisions have been stumbling over this obvious constraint, treating it as if it were a sudoku puzzle rather than a straightforward physical limit. The problem, it turns out, isn't the physics. It's the mathematics.

A new paper by researchers at the Chinese University of Hong Kong (Shenzhen) and The Hong Kong Polytechnic University has cracked open this paradox. They've discovered something counterintuitive: sometimes, the impossible solution — the one where a battery charges and discharges at the same time — isn't actually wrong. It's just a mathematical artifact. And once you understand why, you can fix it in seconds, recover the true optimal solution, and do it all far faster than the conventional approach.

The finding rests on a deceptively simple insight: simultaneous charging and discharging in a mathematical model doesn't always signal a failure. Sometimes it's just noise — a quirk of how the optimization algorithm explores the solution space. And the difference between the two cases comes down to something the researchers call the marginal cycling cost.

---

The Science: Why Batteries Break Math

Energy storage systems sit at the heart of the modern grid. They absorb excess electricity when it's abundant and cheap — think solar panels at noon — and release it when it's scarce and expensive — think a summer evening when everyone cranks up their air conditioning. The mathematics of deciding exactly when to do this, and how much to move in each direction, is called power dispatch optimization. It's a problem that sounds dry but carries enormous consequences. Better dispatch means cheaper electricity, fewer blackouts, and more renewable energy integrated into the grid.

The classic formulation uses mixed-integer programming (MIP), a family of optimization techniques powerful enough to model complex real-world decisions. To prevent the simultaneous charging and discharging problem — what researchers call SCD — MIP models introduce a binary variable: a switch that can only be in one of two positions, on or off. Either you're charging or you're discharging. This is called a complementarity constraint, and it makes the model physically realistic.

There's just one problem. MIP is brutally computationally expensive. Each binary switch multiplies the complexity of the search. For a single battery over 24 hours, broken into 15-minute intervals, that's 96 decision points — and the computational time grows exponentially with each one. In practice, this means engineers either accept long solve times (hours or even days for large systems) or they simplify the problem in ways that introduce errors.

An alternative emerged: relaxation. Instead of forcing the binary switch to be exactly on or off, you let it hover anywhere between zero and one — a continuous value representing partial charging or discharging. This converts the MIP into a linear program (LP), which can be solved in polynomial time. LPs are fast, reliable, and well-understood. The trade-off is that the solution space is larger, which means the relaxed model might include physically impossible scenarios.

Here's where the paradox deepens. When the relaxed LP produces a solution with simultaneous charging and discharging, engineers have historically assumed this meant the relaxation had "failed" — that the faster method couldn't be trusted for this problem. The conventional wisdom held that any SCD in the relaxed solution indicated a fundamental gap between the LP's answer and the true MIP optimum.

But Liu, Li, and Guo suspected this wisdom was wrong. Or at least, incomplete.

---

What They Found: The Artifice of Impossible Actions

The researchers set out to understand exactly what SCD in a relaxed solution means — and when it matters. Their approach was to decompose any relaxed charging/discharging pair into two components. The first is what they call the complementary action: the straightforward charging when the battery needs energy, or discharging when it needs to release energy. The second component is a quantity they label z, representing the simultaneous charging and discharging that cancels out in terms of net energy transfer.

Think of it this way: if a battery simultaneously charges at 5 megawatts and discharges at 5 megawatts, the state of charge doesn't change. The energy flows in and out, but the battery remains at the same energy level. This is pure cycling — it consumes capacity and degrades the battery, but accomplishes nothing. It's precisely the kind of waste that real-world operators want to avoid.

The key insight is that this cycling component z can be isolated, studied, and — in many cases — removed without changing the fundamental decision. The researchers proved that any relaxed solution can be uniquely decomposed into its complementary component plus a cycling component z.

To understand when this decomposition matters, they introduced the marginal cycling cost, denoted κ. This number captures the net cost of cycling — what you pay for charging plus what you receive for discharging, adjusted for efficiency losses. The marginal cycling cost is defined as:

$${\kappa }_t^0=C_t^{\text{CH}}+\eta C_t^{\text{DC}}$$

where C represents cost coefficients for charging and discharging, and η is the overall round-trip efficiency (the product of charging and discharging efficiencies).

The sign of κ tells the whole story:

When κ > 0, cycling is strictly penalized. The relaxation will never choose SCD in an optimal solution — it's too expensive. The relaxation is automatically exact.

When κ = 0, cycling has no cost effect. Here, SCD might appear in the solution, but it doesn't change the objective value at all. The solution is what the researchers call degenerate — mathematically different from the true complementary solution, but equally good. You can remove the cycling component and recover an optimal complementary schedule without any loss.

When κ < 0, cycling is actually profitable. This is the only case where SCD matters — where the relaxed solution is exploiting a real advantage that can't be replicated without the binary constraint.

This gives a necessary and sufficient condition for relaxation exactness, which the researchers formalize in Theorem 1. For the relaxation to be optimal-value exact — meaning the LP's answer equals the MIP's answer — it suffices that for every time period, either the marginal cycling cost is non-negative or there's no available headroom for cycling. In practical terms, the exactness condition is:

$$[-{\kappa }_t^0{]}^{+}{\overline{z}}_t(\Delta e_t^{\ast })=0$$

where the bracketed term is the positive part of the negative cycling cost, and z-bar is the maximum feasible cycling amount given the prescribed energy transition.

The physical interpretation is elegant: the gap between the relaxed and original formulations is zero unless cycling is both profitable and physically feasible. If either condition fails, you're safe.

---

The Algorithm: Two Stages to Clarity

Armed with this condition, the researchers designed an algorithm that extracts the best of both worlds: the speed of LP relaxation plus the guarantee of MIP correctness.

Stage 1 is the fully relaxed LP. Solve the problem without any binary constraints and compute the cycling amount z at each time period. If no period with κ < 0 exhibits cycling (i.e., z = 0), you're done. The relaxed solution is already exact, and you can simply remove any SCD at zero-cost periods by setting z = 0.

Stage 2 only triggers if SCD appears at a period where κ < 0 and z > 0. In that case, re-solve the problem with binary constraints imposed only on those problematic periods — not the entire time horizon. The resulting "partial MIP" has far fewer binary variables than the full MIP, which dramatically reduces computational cost. Finally, clean up any remaining SCD at zero-cost periods.

The practical implication is striking: in most cases, the algorithm requires at most one LP and one partial MIP. You're solving a fraction of the original MIP's complexity while guaranteeing the same optimal answer.

To validate their theory, the researchers ran numerical experiments on a five-period energy storage dispatch problem with realistic parameters: round-trip efficiency of 90.25% (accounting for 95% charging and 95% discharging efficiency), power limits of 6 megawatts for both charging and discharging, state-of-charge bounds from 0 to 20 megawatt-hours, and an initial and final state of charge of 10 megawatt-hours. The cost coefficients were chosen to create interesting dynamics — periods where charging is expensive and discharging is lucrative, and vice versa.

The marginal cycling costs across the five periods tell the story:

Marginal Cycling Cost by Period

Label	Value
Period 1	5.4875
Period 2	5.4875
Period 3	-2.0125
Period 4	5.5125
Period 5	0

Notice the contrast: periods 1, 2, and 4 have positive cycling costs, meaning cycling is penalized. Period 3 has a negative cycling cost, making cycling profitable. Period 5 sits exactly at zero — cycling costs nothing.

When the researchers solved the fully relaxed LP, the results confirmed the theory. At period 3, where κ < 0, the model chose SCD with a cycling amount of 3.15 megawatts. This wasn't an artifact — it was profitable arbitrage. The relaxed LP found an objective value of -$35.59, exploiting the price differential across periods. At period 5, where κ = 0, SCD appeared (cycling of 0.77 MW) but was purely mathematical, leaving the objective unchanged.

The full MIP — enforcing binary constraints on all periods — took longer to solve and returned an objective value of -$30.49. This is the true optimum, and it's different from the relaxed LP because the relaxation was actually exploiting profitable SCD at period 3.

The partial MIP, applying binary constraints only at period 3, recovered this same optimum. It took far less time than the full MIP. And when the researchers cleaned up the SCD at period 5 (removing the 0.77 MW of cycling that cost nothing), they recovered a fully complementary schedule — physically realizable, no simultaneous charging and discharging, and the same optimal objective value of -$30.49.

Objective Values Across Solution Methods

Label	Value
Relaxed LP	-35.59
Partial MIP (Stage 2)	-30.49
Recovered Solution	-30.49
Full MIP (reference)	-30.49

The numerical results from their experiments demonstrate this progression clearly:

Stage 1 (Relaxed LP):

• Charging/discharging power at each period computed with SCD allowed
• Period 3: charging at 3.15 MW and discharging at 2.85 MW simultaneously
• Period 5: charging at 5.30 MW and discharging at 0.70 MW simultaneously
• Objective: -$35.59

Stage 2 (Partial MIP):

• Binary constraint applied only at period 3
• Period 3: charging at 6 MW, no discharging (complementary)
• Period 5: still shows SCD (charging at 2.45 MW, discharging at 3.45 MW) because κ = 0
• Objective: -$30.49

Stage 3 (Recovered Solution):

• Period 5 SCD removed by setting z = 0
• Period 5: charging at 1.33 MW, discharging at 0 MW
• All periods now fully complementary
• Objective: -$30.49 (unchanged)

Recovered Complementary Schedule

Label	Value
Period 1	0
Period 2	0
Period 3	6
Period 4	6
Period 5	1.33

The recovered complementary solution shows clean, implementable schedules. Period 3 charges at full capacity (6 MW), taking advantage of the low charging cost. Periods 1 and 2 discharge to capture high discharging revenues. Period 4 charges at full capacity, exploiting the low charging cost. Period 5 makes a small adjustment — 1.33 MW charge, no discharge — to return to the required final state of charge of 10 MWh.

---

Why This Changes Things: Beyond the Textbook Problem

The implications extend well beyond this elegant theoretical result. Energy storage is rapidly becoming the backbone of modern power grids. The U.S. added a record 31.3 gigawatts of battery storage in 2024, with projections suggesting the installed base could reach 200 gigawatts by 2030. China has already surpassed 100 gigawatts. Europe is accelerating storage deployment to meet its renewable integration targets. Every percentage point of efficiency in dispatch optimization translates to billions of dollars in value over the coming decades.

Current practice varies widely. Some operators run full MIP for critical decisions, accepting hour-long solve times for systems that could be optimized in seconds. Others use heuristic rules — simplified decision frameworks that sacrifice optimality for speed. The gap between what we could achieve and what we do achieve is substantial.

The Liu-Li-Guo condition offers a principled way to bridge this gap. By checking the sign of the marginal cycling cost, operators can immediately determine whether a relaxed solution is trustworthy. If κ ≥ 0 everywhere, the LP is exact, and you can use it confidently. If κ < 0 periods exist, you know exactly which ones need binary constraints — often just a few in a 96-period horizon.

This matters for several practical scenarios:

Real-time dispatch requires decisions in seconds, not minutes. An LP solve taking a few seconds is acceptable; a MIP solve taking an hour is not. The algorithm can identify when LP relaxation is safe, enabling real-time deployment of optimal schedules.

Stochastic optimization, where you must evaluate thousands of scenarios to account for uncertainty, multiplies the computational burden of MIP dramatically. If the condition holds across scenarios, LP relaxation could be used for scenario evaluation, with MIP reserved for final solution.

Network-constrained problems, where storage decisions interact with transmission limits and generator commitments, are even more complex. The researchers note that extending the condition to these settings is a key direction for future work. If successful, the computational savings would multiply, since network constraints are where MIP truly struggles.

The condition also illuminates a deeper point about the nature of optimization in energy systems. The researchers show that the relaxation gap — the potential difference between the LP and MIP answers — is governed entirely by the product of the negative cycling cost and the available cycling headroom. This is a structural quantity that depends on prices, efficiency, and power limits, not on solution technique. It's a property of the problem, not a limitation of the solver.

This reframing matters for how we think about algorithmic development. Instead of designing increasingly sophisticated solvers to handle binary constraints faster, engineers can analyze the problem structure to determine when binary constraints matter at all. The answer, it turns out, depends on a single number per time period: the marginal cycling cost.

---

What's Next: From Theory to Grid

The paper leaves several threads for future exploration. Most directly, the researchers propose extending the theory to network-constrained power system optimization — the setting where generation, transmission, and storage are co-optimized. This is the regime where MIP's computational burden is most acute and where the potential savings from their approach are largest.

The practical implementation will require software integration. commercial optimization packages like Gurobi, CPLEX, or open-source alternatives like HiGHS would need interfaces that check the exactness condition and selectively apply binary constraints. This is engineering work, not theoretical work, but it will determine whether the approach reaches practitioners.

The researchers also acknowledge limitations in their analysis. The necessary and sufficient condition applies to the single-storage, single-period case they studied. Whether it extends cleanly to multiple interacting storage assets, to problems with commitment constraints on generators, or to settings with uncertainty remains to be shown. The proofs rely on structural properties of the optimization problem that may or may not hold in more general settings.

There's also the question of what happens when the problem data — prices, efficiency factors, power limits — varies continuously rather than being fixed for each period. In real markets, these parameters change. The condition presumably must be re-checked each time a new problem is solved, but the computational overhead of checking it should be minimal compared to the solve time savings it enables.

Finally, the paper opens questions about how practitioners should model efficiency losses. The current formulation assumes constant efficiency factors across operating conditions. Real batteries have efficiency curves that depend on charge and discharge rates, temperature, and state of charge. The marginal cycling cost would need to be recomputed as a function rather than a scalar in these more detailed models. Whether the clean theoretical structure survives this generalization is an open question.

---

A Small Number, A Big Implication

The most striking number in the paper isn't dramatic by typical metrics — it's not a billion-dollar savings estimate or a terawatt-hour of storage deployed. It's simply the marginal cycling cost κ for each period in the numerical example: 5.49, 5.49, -2.01, 5.51, and 0.00.

These five numbers — derived from prices and efficiencies — tell you everything about whether the fast method works. They tell you that at period 3, you need the binary constraint. They tell you that at period 5, the simultaneous charging and discharging is just a mathematical phantom, removable without consequence. They tell you that for periods 1, 2, and 4, you never needed the binary constraint at all.

This is the power of good theory: it turns a search problem into a calculation. Instead of solving a complex optimization and then checking whether the answer is valid, you can check the problem structure first and know, before you solve, which approach will work.

The paper's final sentence points toward the larger vision: "Future work will integrate this theory into network-constrained power system optimization problems." If successful, it would bring the computational benefits of relaxation — which can be orders of magnitude faster than MIP — to the kinds of massive planning models that utilities and grid operators use every day.

The humble battery, it turns out, has been waiting for someone to notice that the obvious thing — that you can't charge and discharge at the same time — isn't always the obvious constraint. Sometimes it's just a math artifact. And once you see the difference, the solution becomes clear.