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)