Pattern-Database Pricing Tables for Coupled Online Allocation

Many online allocation problems use the same simple mechanism. A shadow price is attached to each scarce resource, and it rises as the resource fills. Each arriving request is accepted only if its value beats the current total price of what it would consume. When there is a single resource and requests are tiny, theory gives the exact best shape for this price curve: characterize the worst possible input sequence, write down a differential equation, and solve it. That recipe breaks down in the settings that matter in practice. An electric-vehicle (EV) charging station has a daily energy budget, a per-hour power cap, and transformer limits all at once, and a single car is a sizable fraction of an hourly cap. The authors of the charging work say plainly that for such coupled, multi-dimensional problems, finding the worst-case instance becomes intractable. At that point the principled design method falls back to loose generic bounds.

Heuristic search met the same obstacle decades ago and solved it with pattern databases. A pattern database handles a state space too large to analyze by exactly solving a small projection of it offline, storing the answers in a lookup table, and combining several tables at query time in a way that provably keeps a valid bound. We propose to carry this construction into online allocation. The pricing policy becomes a set of lookup tables, one for each small group of coupled resources (a "pattern"). Each table is computed offline by exhaustively solving a discretized worst-case design problem restricted to that pattern. The tables are then summed at run time under a partitioning rule, borrowed from cost partitioning in planning, which guarantees that the combined policy carries a computable competitive-ratio certificate. A competitive ratio is the worst-case factor by which the online algorithm can fall short of an omniscient offline optimum.

Core Claim

The online primal-dual certificate that underlies threshold algorithms is additive over resources in the same way that admissibility is additive over abstractions. The certificate compares, step by step, what the algorithm gains against the growth of a dual upper bound on the offline optimum. For a candidate ratio $\alpha$ it requires, at every arrival $t$,

$$P_t - P_{t-1} \;\ge\; \tfrac{1}{\alpha}\,(D_t - D_{t-1}),$$

where $P_t$ is the algorithm's accumulated value and $D_t$ is a feasible dual objective built from the current prices. Together with dual feasibility at the end, this gives $\mathrm{OPT} \le D_T \le \alpha P_T$.

On a discretized utilization grid, this condition becomes a finite set of linear inequalities in the table entries. That turns price design from solving a differential equation into solving a linear program (LP), and the LP can be solved exactly for low-dimensional patterns. We then price a request $j$ with resource consumption $a_{jr}$ as

$$\pi(j) \;=\; \sum_{S} \sum_{r \in S} a_{jr}\,\phi_{S,r}(u_S).$$

Here $S$ ranges over patterns, $u_S$ is the current joint utilization of the resources in $S$, and $\phi_{S,r}$ is the stored marginal price for resource $r$ inside pattern $S$.

The claim we will prove is a certificate-additivity lemma. Suppose each resource's capacity term in the dual, and each request's value, is partitioned across patterns with shares summing to at most the whole. Suppose also that each pattern's table satisfies its local certificate at ratio $\alpha$ on its share. Then the summed policy satisfies the global certificate at ratio $\alpha$. We allow shares to be negative, following From Non-Negative to General Operator Cost Partitioning.

The payoff comes from joint patterns. Take a pattern such as "daily energy budget together with the 6pm rate cap." Its table can raise prices before the rate cap binds, because it can see that the budget is also tight. A sum of one-resource curves cannot do this. The grid also represents discrete item sizes directly, so the method does not need the infinitesimal-item assumption behind existing optimality proofs.

Relation to Prior Work

The allocation side motivates the problem and supplies the certificate. Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging and ORC derive threshold functions by instance-dependent primal-dual analysis for fractional multiple knapsack with rate constraints. They reach a ratio between $1+\ln\theta$ and $2+\ln\theta$, where $\theta$ is the value fluctuation ratio. ORC names worst-case characterization in coupled settings as the obstacle. We replace the analytic characterization with exhaustive offline solution over abstractions.

Cap-and-Penalize is optimal for a single pool with multi-phase penalties but only $O(2+\ln\Delta)$ under per-step caps, where $\Delta$ is the ratio of maximum to minimum valuation. That open gap is exactly a coupling between a global and a per-step constraint, and our joint patterns target it.

Online Knapsack with Frequency Predictions both motivates and constrains the design. It shows that offline precomputation of budget curves helps a great deal. It also proves that pure threshold rules cannot be optimal once predictions are available. Our tables are thresholds over joint utilization, so we restrict our claims to the prediction-free worst-case setting and do not claim to beat SENTINEL, its budget-tracking algorithm.

The search side supplies the method. Finding Optimal Solutions to Rubik's Cube Using Pattern Databases established solving a projection exhaustively offline and looking it up online. General cost partitioning supplies the additive-combination rule and the evidence that negative shares tighten bounds: 630 versus 442 tasks solved. Implicit Abstraction Heuristics shows that expensive structured solutions can be databased so that online evaluation is trivial. PDBs Go Numeric shows how to bound and discretize numeric resource variables. It also warns that orthogonality breaks when actions share numeric variables, which is precisely our situation and the reason we need partitioning rather than naive summation.

The closest cross-over work is An Exact Best-First Search Procedure for the Constrained Rectangular Guillotine Knapsack Problem. It precomputes a dynamic-programming table to bound an offline two-dimensional knapsack. It has no arrivals, no irrevocability and no competitive guarantee, whereas our tables are online pricing policies with certificates.

Research Program

The work has three parts. The first is theory. We will prove the certificate-additivity lemma for packing problems with linear consumption. We will then characterize when joint patterns strictly improve the achievable $\alpha$ over atomic (single-resource) patterns. We start with the simplest coupled case, one aggregate budget plus per-slot rate caps, where the reference numbers $1+\ln\theta$ and $2+\ln\theta$ are known.

The second is construction. For each pattern we discretize joint utilization into a grid. Item sizes are taken from the empirical session distribution, so large discrete items are represented directly. We solve the certificate LP, binary-searching on $\alpha$, and store the resulting price table. A second LP chooses the partition shares across patterns, mirroring optimal cost partitioning. Pattern selection is a greedy search over resource subsets under a memory budget, analogous to automated pattern selection in Automatic Generation of Memory Based Search Heuristics.

The third is certification. We need to measure true worst-case behavior independently of our own certificate. To do so we build an exact adversary search. For a fixed policy on small instances, it searches over request sequences for the one maximizing the ratio of the offline optimum to the online value. It prunes with an upper bound on the ratio still achievable, and that bound is itself precomputed by abstraction. The search gives an empirical worst-case ratio that is independent of the certificate being tested.

Baselines

The naive reference points are a fixed threshold algorithm and greedy dispatch. The fixed threshold algorithm is a single static price computed from value extremes, as used in the EV-charging papers. Greedy dispatch means earliest-deadline-first and least-laxity-first as implemented in ACN-Sim. The file reports that these break down under coupled limits: ACN-Sim reports line and transformer violations for earliest-deadline-first and least-laxity-first. Anything that fails to beat them clearly is dead on arrival.

The strongest existing method on the charging question is the online threshold algorithm (OTA) of Competitive Algorithms for the Online Multiple Knapsack Problem. It is the only one designed for exactly the budget-plus-rate coupling. The reported margin is a 40–44% decrease in the profit-ratio gap relative to the fixed threshold algorithm. ORC breaks the worst-case empirical profit ratio down by congestion level: 44.4% improvement under high congestion, 33.3% under medium and 10.0% under low, with about 20% average improvement in high load. We found no reported absolute profit-ratio values on Lacuna, only relative improvements. We will therefore reimplement OTA and the fixed threshold algorithm and first reproduce these relative gaps before comparing.

On the penalty benchmark, the strong baseline is PPM-$\Phi$, the posted-price mechanism of Cap-and-Penalize with its bound of $O(2+\ln\Delta)$ under per-step caps. We found no reported numeric per-step competitive ratio on Lacuna for it.

All methods receive the same fairness conditions. They see the same ACN session sequences (2,000 sessions, 24 one-hour slots, three congestion levels). They share the same value bounds $L$ and $U$. Any method with offline tuning receives the same number of offline solver or simulator calls as our table construction.

Beating OTA means two things together. The first is a strictly smaller certified worst-case ratio, from adversary search, on the discrete-item instance class. The second is no loss in average profit ratio on traces. Beating it on only one axis will be reported as a partial result.

Two ablations isolate the key ingredient. The first uses atomic patterns only: the same LP pipeline, but every table sees a single resource. The second uses joint patterns with non-negative shares only. If atomic tables do as well as joint ones, the joint-abstraction idea contributes nothing. The comparison with non-negative shares tests whether general partitioning matters, as it did in planning.

Why not just…?

Why not just use separable per-resource thresholds, i.e. OTA extended resource by resource? This is the most serious threat. OTA is already within an additive 1 of optimal in the fractional case. Our argument is that the remaining gap and the large-item degradation both come from coupling and discreteness, and a separable price cannot see either. That is an argument, not evidence. The atomic-pattern ablation settles it directly: if joint patterns fail to lower the certified ratio on instances small enough to solve the full joint game exactly, we drop the claim.

Why not just tune threshold curves by black-box optimization on historical ACN traces? Trace tuning may match or beat us on average profit, because it fits the actual arrival distribution. It carries no worst-case guarantee, and the file gives no evidence either way. We will give the tuner the same compute budget and evaluate it under the adversary search. If the tuned curves also hold up adversarially, the value of our construction shrinks to interpretability and certification, and we will say so.

Why not just solve an LP at every arrival, model-predictive style? Per-step solving is the natural upper-quality reference, but it costs heavily at run time. In planning, per-state LPs took 17 minutes against under 1 minute for precomputed potentials on 600 tasks (From Non-Negative to General Operator Cost Partitioning). Databasing fork solutions gained 74 solved instances (Implicit Abstraction Heuristics). Per-step LPs with forecasts also have no competitive guarantee under adversarial arrivals. We report it as a quality reference with per-decision latency alongside.

Why not just solve the full joint grid, with no abstraction? On toy instances we will do exactly that. It is our ground truth for how much the pattern abstraction loses. The joint grid grows exponentially in the number of coupled resources, the same memory wall that motivated pattern databases, so it cannot scale to a 24-slot station with phase limits.

Proposed Experiments

The first decisive check runs on small synthetic budget-plus-rate instances with discrete item sizes, where both the full joint certificate LP and the exact adversary search are tractable. There we compare certified and empirically worst ratios for the full joint table, the pattern-additive table, atomic tables, OTA, and the fixed threshold algorithm. The prediction is an ordering from best to worst: the full joint table, then the pattern tables close behind, then atomic tables and OTA noticeably worse as item size grows relative to the rate cap. We also check whether the computed ratio for the fractional limit falls strictly below $2+\ln\theta$. That would narrow the open gap numerically and suggest what the analytic answer should be.

The second check runs on the Cap-and-Penalize synthetic setting with per-step caps. It asks whether a pattern pairing the global penalty pool with each step's cap beats the $O(2+\ln\Delta)$ mechanism in computed worst-case ratio.

The third check is trace-driven on ACN-Data through ACN-Sim at low, medium and high congestion. It reports profit ratio against the offline optimum, the worst case over sequences, and constraint violations. It adds transformer and phase limits as extra resources to test scaling in the number of patterns. Success on this check requires reproducing OTA's reported margin over the fixed threshold algorithm and then improving the worst-case gap further under high congestion, where coupling binds most.

We will report table memory and per-decision latency for every method, since constant-time lookup is the reason to precompute at all.