HyperFlow / backend /flagship /split.py
Gaurav711's picture
Deploy 891f179
2b86c60 verified
Raw History Blame Contribute Delete
8.42 kB
"""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)