// 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 } export interface SplitResult { status: 'optimal' | 'infeasible'; assignment: Record; storeTotalsMinor: Record; 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): 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(); 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>; function price(assignment: Record, costs: Costs, stores: Record) { const subtotals = new Map(); for (const [id, s] of Object.entries(assignment)) subtotals.set(s, (subtotals.get(s) ?? 0) + costs.get(id)!.get(s)!); const totals: Record = {}; 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, costs: Costs, stores: Record, 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): SplitResult { validate(items, stores); const costs: Costs = new Map(); const unpurchasable: string[] = []; for (const it of items) { const allowed = new Map(); 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 = {}; 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); }