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);
}