What does Routing Periodic Quotas conclude, in numbers, about “Greedy against Linear Programming: Random Arrival, Prices Learned from a Sample, and Drift”?

Answer: Chapter 6 compares rules under random arrival: arrival order averages 0.8427 of the hindsight optimum, dynamic re-solving at geometric checkpoints 0.9875.

Scope of the numbers: Under illustrative parameters the linear programme gains 0.1668 to 0.2217 over arrival order, but only 0.41 % to 5.05 % over a fixed rule that sorts by complexity; most of the gain comes from sorting itself. Parameters are illustrative and contain no vendor's prices or quotas; all calculations are generated by the book's programs.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.8427, 0.9875

policy mean ratio 5th pct worst (200 cycles, eps 0.1)
greedy0.84270.81560.8026
one-shot0.96550.90000.8709
dynamic0.98750.96650.9508
Show the full program
# Chapter 6. p61: first-come greedy, a learned plan, and hindsight.
# Model: a cycle of N = 530 tasks drawn one by one from the class mix
# (300, 150, 60, 20)/530, in random order, quotas H 600 and F 900.
#   greedy   - every task tries H first, then F
#   one-shot - the first 10 percent go by the fixed rule; then one LP
#              on the observed counts, with the remaining quota scaled
#              to the sample and shaved by the sample share, gives per
#              class H shares used as routing probabilities
#   dynamic  - the same, re-solved at 10, 20, 40 and 80 percent of the
#              cycle (the doubling schedule of Agrawal, Wang and Ye)
#   offline  - the LP on the realised counts, known only in hindsight
# 200 seeded cycles; ratios are to the offline optimum. Illustrative.
import math
import random
from fractions import Fraction as Fr

def simplex(c, A, b, rule="bland", cap=500):
    m, n = len(A), len(c)
    T = [[Fr(v) for v in A[i]] + [Fr(int(i == j)) for j in range(m)]
         + [Fr(b[i])] for i in range(m)]
    z = [-Fr(v) for v in c] + [Fr(0)] * (m + 1)
    basis = [n + i for i in range(m)]
    steps = 0
    while steps < cap:
        cols = [j for j in range(n + m) if z[j] < 0]
        if not cols:
            break
        if rule == "bland":
            e = cols[0]
        else:
            e = min(cols, key=lambda j: (z[j], j))
        rows = [i for i in range(m) if T[i][e] > 0]
        if not rows:
            return None
        r = min(rows, key=lambda i: (T[i][-1] / T[i][e], basis[i]))
        p = T[r][e]
        T[r] = [v / p for v in T[r]]
        for i in range(m):
            if i != r and T[i][e] != 0:
                f = T[i][e]
                T[i] = [a - f * w for a, w in zip(T[i], T[r])]
        f = z[e]
        z = [a - f * w for a, w in zip(z, T[r])]
        basis[r] = e
        steps += 1
    x = [Fr(0)] * (n + m)
    for i, j in enumerate(basis):
        x[j] = T[i][-1]
    return x[:n], z[-1], z[n:n + m], steps


VALUE = (1, 2, 5, 10)
COST = {"H": (4, 6, 10, 16), "F": (1, 2, 3, 4)}
SUCC = {"H": ("0.97", "0.95", "0.90", "0.85"),
        "F": ("0.95", "0.80", "0.45", "0.15")}
RW = {t: [VALUE[k] * Fr(SUCC[t][k]) for k in range(4)] for t in "HF"}
Q = {"H": 600, "F": 900}
N = 530
MIX = (300, 150, 60, 20)


def lp(counts, q):
    c = [RW[t][k] for t in "HF" for k in range(4)]
    A = [[COST["H"][k] if t == "H" else 0 for t in "HF" for k in range(4)],
         [COST["F"][k] if t == "F" else 0 for t in "HF" for k in range(4)]]
    b = [q["H"], q["F"]]
    for k in range(4):
        A.append([1 if j == k else 0 for t in "HF" for j in range(4)])
        b.append(counts[k])
    x, val, _, _ = simplex(c, A, b)
    share = [x[k] / counts[k] if counts[k] else Fr(1, 2) for k in range(4)]
    return val, share


def draw(rng, mix_a, mix_b):
    out = []
    for i in range(N):
        mix = mix_a if i < N // 2 else mix_b
        out.append(rng.choices(range(4), weights=mix)[0])
    return out


def serve(k, first, left):
    for t in first:
        if left[t] >= COST[t][k]:
            left[t] -= COST[t][k]
            return RW[t][k]
    return Fr(0)


def online(tasks, policy, eps, rng):
    left = dict(Q)
    got = Fr(0)
    cut = max(1, int(eps * N))
    share = None
    nxt = cut
    for i, k in enumerate(tasks):
        if policy == "greedy":
            got += serve(k, "HF", left)
            continue
        if i < cut:
            got += serve(k, "HF" if k >= 2 else "FH", left)
            continue
        if share is None or (policy == "dynamic" and i == nxt):
            seen = [tasks[:i].count(j) for j in range(4)]
            scale = Fr(N - i, i)
            room = (1 - Fr(cut, N)) if policy == "dynamic" else 1 - eps
            q = {t: Fr(left[t]) * room / scale for t in "HF"}
            share = lp(seen, q)[1]
            nxt = 2 * i
        first = "HF" if rng.random() < share[k] else "FH"
        got += serve(k, first, left)
    return got

rng = random.Random(20261113)
res = {p: [] for p in ("greedy", "one-shot", "dynamic")}
for trial in range(200):
    tasks = draw(rng, MIX, MIX)
    best = lp([tasks.count(j) for j in range(4)], Q)[0]
    for p in res:
        got = online(tasks, p, Fr(1, 10), rng)
        res[p].append(float(got / best))
print("policy     mean ratio  5th pct  worst   (200 cycles, eps 0.1)")
for p, v in res.items():
    v = sorted(v)
    print("%-9s  %10.4f  %7.4f  %6.4f" % (p, math.fsum(v) / len(v),
                                          v[9], v[0]))

Single source and citation

Fan, Y. (2026). Peak-Shaving Periodic Quotas and Cross-Model Routing: Linear Programming against Reset Countdowns to Split Work between Heavy-Reasoning and Fast Models (Version 1.0.0), Chapter 6: Greedy against Linear Programming: Random Arrival, Prices Learned from a Sample, and Drift. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-270 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026270,
  author    = {Fan, Yafu},
  title     = {Peak-Shaving Periodic Quotas and Cross-Model Routing: Linear Programming against Reset Countdowns to Split Work between Heavy-Reasoning and Fast Models},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book