File size: 8,424 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 160 161 162 163 164 165 166 167 168 | """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)
|