File size: 7,915 Bytes
2b86c60 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 | // 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);
}
|