"""Cheapest way to split one basket across stores, including per-store fees. Each store charges a handling fee when used, a delivery fee unless its subtotal reaches a free-delivery threshold (no threshold: always charged), and a small-cart fee while its subtotal is below a small-cart threshold (no threshold: never charged). Money is integer minor units throughout. """ import itertools import numpy as np from scipy.optimize import Bounds, LinearConstraint, milp STORE_FIELDS = ('delivery_fee_minor', 'free_delivery_threshold_minor', 'handling_fee_minor', 'small_cart_fee_minor', 'small_cart_threshold_minor') OPTIONAL = {'free_delivery_threshold_minor', 'small_cart_threshold_minor'} MAX_ITEMS, MAX_STORES = 50, 6 def _money(value, optional=False): if optional and value is None: return True return isinstance(value, int) and not isinstance(value, bool) and 0 <= value <= 10**10 def _validate(items, stores): if not isinstance(stores, dict) or not 1 <= len(stores) <= MAX_STORES: raise ValueError(f'Provide 1 to {MAX_STORES} stores') for name, fees in stores.items(): if not isinstance(name, str) or not isinstance(fees, dict) or set(fees) != set(STORE_FIELDS): raise ValueError('Each store needs exactly the documented fee fields') if not all(_money(fees[f], f in OPTIONAL) for f in STORE_FIELDS): raise ValueError('Store fees and thresholds must be nonnegative integers in minor units') if not isinstance(items, list) or not 1 <= len(items) <= MAX_ITEMS: raise ValueError(f'Provide 1 to {MAX_ITEMS} items') seen = set() for it in items: if not isinstance(it, dict) or not isinstance(it.get('id'), str) or not it['id'] or it['id'] in seen: raise ValueError('Items need unique nonempty string ids') seen.add(it['id']) quantity = it.get('quantity') if not isinstance(quantity, int) or isinstance(quantity, bool) or not 1 <= quantity <= 10000: raise ValueError('Item quantity must be a positive integer') offers = it.get('offers') if not isinstance(offers, dict) or not set(offers) <= set(stores): raise ValueError('Offers must reference known stores') for o in offers.values(): limit = o.get('purchase_limit') if isinstance(o, dict) else None if (not isinstance(o, dict) or not _money(o.get('price_minor')) or not isinstance(o.get('available'), bool) or not isinstance(limit, int) or isinstance(limit, bool) or not 1 <= limit <= 10000): raise ValueError('Offers need integer minor prices, an available flag and a positive purchase limit') def _allowed(it): return {s: o['price_minor'] * it['quantity'] for s, o in it['offers'].items() if o['available'] and it['quantity'] <= o['purchase_limit']} def _store_total(fees, subtotal): free = fees['free_delivery_threshold_minor'] small = fees['small_cart_threshold_minor'] return (subtotal + fees['handling_fee_minor'] + (fees['delivery_fee_minor'] if free is None or subtotal < free else 0) + (fees['small_cart_fee_minor'] if small is not None and subtotal < small else 0)) def _price(assignment, costs, stores): """Store totals and grand total for a complete assignment; shared by the solver and the oracle.""" subtotals = {} for item_id, s in assignment.items(): subtotals[s] = subtotals.get(s, 0) + costs[item_id][s] totals = {s: _store_total(stores[s], sub) for s, sub in sorted(subtotals.items())} return totals, sum(totals.values()) def _result(assignment, costs, stores, unpurchasable): if not assignment: return {'status': 'infeasible', 'assignment': {}, 'store_totals_minor': {}, 'total_minor': None, 'best_single_store': {'store': None, 'total_minor': None}, 'savings_minor': None, 'unpurchasable': unpurchasable} totals, total = _price(assignment, costs, stores) singles = [(_price({i: s for i in assignment}, costs, stores)[1], s) for s in stores if all(s in costs[i] for i in assignment)] best = min(singles) if singles else None return {'status': 'optimal', 'assignment': dict(sorted(assignment.items())), 'store_totals_minor': totals, 'total_minor': total, 'best_single_store': {'store': best[1], 'total_minor': best[0]} if best else {'store': None, 'total_minor': None}, 'savings_minor': best[0] - total if best else None, 'unpurchasable': unpurchasable} def _prepare(items, stores): _validate(items, stores) costs = {it['id']: _allowed(it) for it in items} unpurchasable = [i for i, c in costs.items() if not c] return {i: c for i, c in costs.items() if c}, unpurchasable def solve_split(items, stores): costs, unpurchasable = _prepare(items, stores) if not costs: return _result({}, costs, stores, unpurchasable) ids, names = list(costs), list(stores) n, m = len(ids), len(names) # Variables: x[i,s] (n*m), then used u[s], free-delivery f[s], not-small-cart c[s]. X, U, F, C = 0, n * m, n * m + m, n * m + 2 * m size = n * m + 3 * m cost, upper = np.zeros(size), np.ones(size) rows, low, high = [], [], [] def row(coefficients, lo, hi): r = np.zeros(size) for index, value in coefficients: r[index] += value rows.append(r), low.append(lo), high.append(hi) for i, item_id in enumerate(ids): for s, name in enumerate(names): k = X + i * m + s if name in costs[item_id]: cost[k] = costs[item_id][name] row([(k, 1), (U + s, -1)], -np.inf, 0) # buy only from a used store else: upper[k] = 0 row([(X + i * m + s, 1) for s in range(m)], 1, 1) for s, name in enumerate(names): fees = stores[name] subtotal = [(X + i * m + s, -cost[X + i * m + s]) for i in range(n)] cost[U + s] = fees['handling_fee_minor'] + fees['delivery_fee_minor'] + fees['small_cart_fee_minor'] cost[F + s] = -fees['delivery_fee_minor'] cost[C + s] = -fees['small_cart_fee_minor'] row([(F + s, 1), (U + s, -1)], -np.inf, 0) row([(C + s, 1), (U + s, -1)], -np.inf, 0) if fees['free_delivery_threshold_minor'] is None: upper[F + s] = 0 else: row([(F + s, fees['free_delivery_threshold_minor'])] + subtotal, -np.inf, 0) if fees['small_cart_threshold_minor'] is None: row([(C + s, 1), (U + s, -1)], 0, 0) # never charged: waiver tracks use else: row([(C + s, fees['small_cart_threshold_minor'])] + subtotal, -np.inf, 0) result = milp(cost, integrality=np.ones(size), bounds=Bounds(np.zeros(size), upper), constraints=LinearConstraint(np.array(rows), low, high), options={'time_limit': 5, 'presolve': False, 'mip_rel_gap': 0.0}) if not result.success or result.x is None: raise RuntimeError('Split solver did not reach a verified optimum') x = np.rint(result.x[:n * m]).reshape(n, m) assignment = {} for i, item_id in enumerate(ids): chosen = [names[s] for s in range(m) if x[i, s] == 1] if len(chosen) != 1 or chosen[0] not in costs[item_id]: raise RuntimeError('Split solver returned an invalid assignment') assignment[item_id] = chosen[0] # Independent check: re-price the assignment and require it to match the solver's objective. if _price(assignment, costs, stores)[1] != round(result.fun): raise RuntimeError('Split solver objective failed independent re-pricing') return _result(assignment, costs, stores, unpurchasable) def brute_force_split(items, stores, max_items=8): """Exhaustive oracle over every store choice per item, for small instances only.""" costs, unpurchasable = _prepare(items, stores) if len(costs) > max_items: raise ValueError(f'Brute force is limited to {max_items} purchasable items') if not costs: return _result({}, costs, stores, unpurchasable) ids = list(costs) best = min((_price(dict(zip(ids, combo)), costs, stores)[1], combo) for combo in itertools.product(*(sorted(costs[i]) for i in ids))) return _result(dict(zip(ids, best[1])), costs, stores, unpurchasable)