HyperFlow / extension /src /split.ts
Gaurav711's picture
Deploy 891f179
2b86c60 verified
Raw History Blame Contribute Delete
7.92 kB
// In-browser twin of backend/flagship/split.py. Same model and fee rules; CI checks both against the
// same exhaustive-oracle vectors. Money is integer paise.
import type { Highs } from 'highs';
export interface StoreFees {
deliveryFeeMinor: number;
freeDeliveryThresholdMinor: number | null; // null: delivery always charged
handlingFeeMinor: number;
smallCartFeeMinor: number;
smallCartThresholdMinor: number | null; // null: small-cart fee never charged
}
export interface Offer { priceMinor: number; available: boolean; purchaseLimit: number }
export interface SplitItem { id: string; quantity: number; offers: Record<string, Offer> }
export interface SplitResult {
status: 'optimal' | 'infeasible';
assignment: Record<string, string>;
storeTotalsMinor: Record<string, number>;
totalMinor: number | null;
bestSingleStore: { store: string | null; totalMinor: number | null };
savingsMinor: number | null;
unpurchasable: string[];
}
const MAX_ITEMS = 50;
const MAX_STORES = 6;
const isMoney = (v: unknown): v is number => Number.isSafeInteger(v) && (v as number) >= 0 && (v as number) <= 1e10;
const isCount = (v: unknown): v is number => Number.isSafeInteger(v) && (v as number) >= 1 && (v as number) <= 10000;
function validate(items: SplitItem[], stores: Record<string, StoreFees>): void {
const names = Object.keys(stores);
if (names.length < 1 || names.length > MAX_STORES) throw new Error(`Provide 1 to ${MAX_STORES} stores`);
for (const f of Object.values(stores)) {
const thresholdsOk = [f.freeDeliveryThresholdMinor, f.smallCartThresholdMinor].every((t) => t === null || isMoney(t));
if (!isMoney(f.deliveryFeeMinor) || !isMoney(f.handlingFeeMinor) || !isMoney(f.smallCartFeeMinor) || !thresholdsOk) {
throw new Error('Store fees and thresholds must be nonnegative integers in paise');
}
}
if (items.length < 1 || items.length > MAX_ITEMS) throw new Error(`Provide 1 to ${MAX_ITEMS} items`);
const seen = new Set<string>();
for (const it of items) {
if (!it.id || seen.has(it.id)) throw new Error('Items need unique nonempty ids');
seen.add(it.id);
if (!isCount(it.quantity)) throw new Error('Item quantity must be a positive integer');
for (const [store, o] of Object.entries(it.offers)) {
if (!(store in stores)) throw new Error('Offers must reference known stores');
if (!isMoney(o.priceMinor) || typeof o.available !== 'boolean' || !isCount(o.purchaseLimit)) {
throw new Error('Offers need integer paise prices, an available flag and a positive purchase limit');
}
}
}
}
function storeTotal(f: StoreFees, subtotal: number): number {
const delivery = f.freeDeliveryThresholdMinor === null || subtotal < f.freeDeliveryThresholdMinor ? f.deliveryFeeMinor : 0;
const small = f.smallCartThresholdMinor !== null && subtotal < f.smallCartThresholdMinor ? f.smallCartFeeMinor : 0;
return subtotal + f.handlingFeeMinor + delivery + small;
}
type Costs = Map<string, Map<string, number>>;
function price(assignment: Record<string, string>, costs: Costs, stores: Record<string, StoreFees>) {
const subtotals = new Map<string, number>();
for (const [id, s] of Object.entries(assignment)) subtotals.set(s, (subtotals.get(s) ?? 0) + costs.get(id)!.get(s)!);
const totals: Record<string, number> = {};
for (const s of [...subtotals.keys()].sort()) totals[s] = storeTotal(stores[s]!, subtotals.get(s)!);
return { totals, total: Object.values(totals).reduce((a, b) => a + b, 0) };
}
function result(assignment: Record<string, string>, costs: Costs, stores: Record<string, StoreFees>, unpurchasable: string[]): SplitResult {
const ids = Object.keys(assignment).sort();
if (!ids.length) {
return { status: 'infeasible', assignment: {}, storeTotalsMinor: {}, totalMinor: null,
bestSingleStore: { store: null, totalMinor: null }, savingsMinor: null, unpurchasable };
}
const { totals, total } = price(assignment, costs, stores);
let best: { store: string; totalMinor: number } | null = null;
for (const s of Object.keys(stores).sort()) {
if (!ids.every((id) => costs.get(id)!.has(s))) continue;
const single = price(Object.fromEntries(ids.map((id) => [id, s])), costs, stores).total;
if (!best || single < best.totalMinor) best = { store: s, totalMinor: single };
}
return { status: 'optimal', assignment: Object.fromEntries(ids.map((id) => [id, assignment[id]!])), storeTotalsMinor: totals,
totalMinor: total, bestSingleStore: best ?? { store: null, totalMinor: null },
savingsMinor: best ? best.totalMinor - total : null, unpurchasable };
}
export function solveSplit(highs: Highs, items: SplitItem[], stores: Record<string, StoreFees>): SplitResult {
validate(items, stores);
const costs: Costs = new Map();
const unpurchasable: string[] = [];
for (const it of items) {
const allowed = new Map<string, number>();
for (const [s, o] of Object.entries(it.offers)) {
if (o.available && it.quantity <= o.purchaseLimit) allowed.set(s, o.priceMinor * it.quantity);
}
if (allowed.size) costs.set(it.id, allowed);
else unpurchasable.push(it.id);
}
if (!costs.size) return result({}, costs, stores, unpurchasable);
// LP-format model. Variables: x_i_s (buy item i at store s), u_s (store used),
// f_s (free-delivery threshold met), c_s (small-cart threshold met).
const ids = [...costs.keys()];
const names = Object.keys(stores);
const objective: string[] = [];
const constraints: string[] = [];
const binaries: string[] = [];
const subtotal = names.map(() => [] as string[]);
ids.forEach((id, i) => {
const pick: string[] = [];
names.forEach((s, j) => {
const cost = costs.get(id)!.get(s);
if (cost === undefined) return;
const x = `x_${i}_${j}`;
binaries.push(x);
pick.push(x);
objective.push(`${cost} ${x}`);
subtotal[j]!.push(`${cost} ${x}`);
constraints.push(`${x} - u_${j} <= 0`);
});
constraints.push(`${pick.join(' + ')} = 1`);
});
names.forEach((s, j) => {
const f = stores[s]!;
const small = f.smallCartThresholdMinor === null ? 0 : f.smallCartFeeMinor;
binaries.push(`u_${j}`);
objective.push(`${f.handlingFeeMinor + f.deliveryFeeMinor + small} u_${j}`);
const sub = subtotal[j]!.length ? subtotal[j]!.map((t) => `- ${t}`).join(' ') : '';
if (f.freeDeliveryThresholdMinor !== null) {
binaries.push(`f_${j}`);
objective.push(`- ${f.deliveryFeeMinor} f_${j}`);
constraints.push(`f_${j} - u_${j} <= 0`, `${f.freeDeliveryThresholdMinor} f_${j} ${sub} <= 0`);
}
if (f.smallCartThresholdMinor !== null) {
binaries.push(`c_${j}`);
objective.push(`- ${f.smallCartFeeMinor} c_${j}`);
constraints.push(`c_${j} - u_${j} <= 0`, `${f.smallCartThresholdMinor} c_${j} ${sub} <= 0`);
}
});
const model = ['Minimize', ` obj: ${objective.join(' + ').replace(/\+ -/g, '-')}`, 'Subject To',
...constraints.map((c, k) => ` r${k}: ${c}`), 'Binary', ` ${binaries.join(' ')}`, 'End', ''].join('\n');
const solution = highs.solve(model, { mip_rel_gap: 0, presolve: 'off', time_limit: 5 });
if (solution.Status !== 'Optimal') throw new Error(`Split solver did not reach a verified optimum (${solution.Status})`);
const assignment: Record<string, string> = {};
ids.forEach((id, i) => {
const chosen = names.filter((_, j) => Math.round(solution.Columns[`x_${i}_${j}`]?.Primal ?? 0) === 1);
if (chosen.length !== 1) throw new Error('Split solver returned an invalid assignment');
assignment[id] = chosen[0]!;
});
// Independent check: re-price the assignment and require it to match the solver's objective.
if (price(assignment, costs, stores).total !== Math.round(solution.ObjectiveValue)) {
throw new Error('Split solver objective failed independent re-pricing');
}
return result(assignment, costs, stores, unpurchasable);
}