Basically, the problem we are analyzing in this post here is to change the existing prices of items in the menu by tiny amounts (+/- 2 cents) to maximize the number of (future) customer bills that end with zero or five cents (i.e., $x.05, $x.10, $x.15, ... $x.95) after (13%) tax. Assuming that past transactions (200 of them) are a good indicator of future purchase patterns, we can select a portion of this data (say 60%) to 'train' our pricing model (MIP) on, and then evaluate its performance on the remaining 40% of the transactions.
Model
1. Decision variables: There are five pricing possibilities for the recommended price of an item p(i) = {p0(i)-2, p0(i)-1, p0(i), p0(i)+1, p0(i)+2}, where p0(i) = original price of the item in the menu.
2. Bill(transaction j) b(j) = sum(i) Aij.p(i)*(1+T/100)
where:
a. Aij = number of units of item (i) purchased in historical transaction (j)
b. T = percentage sales tax charged
3.The minimum (l(j)) and maximum (u(j)) values for b can be determined by setting all prices to their lower bounds, and upper bounds respectively. We assume that fractional cents are rounded to the nearest cent. This gives a pre-computable range of feasible b values V(j) = {l(j), l(j)+1, ...., u(j)}.
4. Objective: Maximize the number of times b ends in 0 or 5 (using boolean indicator variable 'z' and 0-1 cost 'c') in the training set by selecting one price from the 5 possibilities for each item
CAFEMIP: Max sum(k,j) c(k,j)z(k,j)
subject to:
ii) sum(i) Aij.p(i)*(1+T/100) = sum(k)V(k, j).z(k, j) for all j
iii) SOS-1 constraints for: prices p(i) that ensure that one of five prices is picked for each item in the menu, and for z(j) to ensure that exactly one bill realization is active for each transaction.
Round-off Issue
The LHS of constraint 4(ii) can contain fractional cents, whereas the RHS only admits discrete values. This situation can be overcome as follows:
b(j) = sum(i) Aij.p(i) + sum(i) Aij.p(i)(T/100) = b'(j) + tax,
where b'(j) is integer. Every realization of b'(j) (=V'(j)) can be mapped to our 0-1 objective function contribution after accounting for the additional tax it generates. Thus, it is sufficient to retain the integer components of 4(ii) and rewrite it free of round-off error as:
sum(i) Aij.p(i) = sum(k)V'(k, j).z(k, j) for all j
CAFEMIP was optimized using CPLEX 12.x and implemented in Java. As a secondary objective, a tiny penalty was added to minimize the deviation of prices from the original value to avoid unnecessary price changes or revenue shifts.
Results
1. optimized over the entire 200 transactions (no hold-out sample).We count the number of times, the cafe needed to round to the nearest 0 or 5 using the prices before and after optimization.
Roundings needed: original price: 135/200
Roundings needed: optimized price: 35/200
While the results on training data are really good, we do not know how well CAFEMIP would do on hidden data, so we re-run CPLEX on a subset of the data.
2. Optimized over the first 120 transactions only, and tested on the last (hidden) 80 transactions.
training data: original cost = 77/120
training data: optimized cost = 20/120
--- CPLEX log ----
Tried aggregator 1 time.
MIP Presolve eliminated 34 rows and 17 columns.
Reduced MIP has 230 rows, 847 columns, and 1824 nonzeros.
Reduced MIP has 835 binaries, 0 generals, 0 SOSs, and 0 indicators.
Probing fixed 68 vars, tightened 0 bounds.
Probing time = 0.01 sec.
Tried aggregator 1 time.
MIP Presolve eliminated 4 rows and 207 columns.
MIP Presolve modified 14 coefficients.
Reduced MIP has 226 rows, 640 columns, and 1666 nonzeros.
Reduced MIP has 629 binaries, 11 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.06 sec.
Probing time = 0.02 sec.
Clique table members: 3071.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 4 threads.
Root relaxation solution time = 0.00 sec.
Nodes Cuts/
Node Left Objective IInf Best Integer Best Node ItCnt Gap
0 0 13.3095 48 13.3095 92
* 0+ 0 73.0000 13.3095 92 81.77%
0 0 18.8333 13 73.0000 Cuts: 130 189 74.20%
0 0 20.0000 2 73.0000 Cuts: 22 220 72.60%
* 0+ 0 20.0000 20.0000 220 0.00%
0 0 cutoff 20.0000 20.0000 220 0.00%
Elapsed real time = 0.16 sec. (tree size = 0.00 MB, solutions = 2)
Clique cuts applied: 34
Cover cuts applied: 35
Implied bound cuts applied: 4
Mixed integer rounding cuts applied: 7
Zero-half cuts applied: 7
Gomory fractional cuts applied: 28
Root node processing (before b&c):
Real time = 0.09
Parallel b&c, 4 threads:
Real time = 0.00
Sync time (average) = 0.00
Wait time (average) = 0.00
-------
Total (root+branch&cut) = 0.09 sec.
CPLEX objval = 20.000000000000025
original, new price of XS Coffee is $1.24, $1.24
original, new price of S Coffee is $1.33, $1.33
original, new price of M Coffee is $1.57, $1.55
original, new price of L Coffee is $1.71, $1.73
original, new price of XL Coffee is $1.91, $1.90
original, new price of S Tea is $1.33, $1.32
original, new price of M Tea is $1.52, $1.51
original, new price of L Tea is $1.71, $1.73
original, new price of Donut is $0.95, $0.97
original, new price of Bagel is $1.24, $1.24
original, new price of Muffin is $1.30, $1.28
original, new price of Cookie is $0.75, $0.75
(prices in red indicate a changed recommendation when optimizing over the partial sample instead of the entire history)
These prices were used to recompute the bills in the hidden sample:
hidden data: original cost = 58/80 (~72%)
hidden data: optimized cost = 17/80 (~21%)
Thus, we would have been able to significantly reduce the number of roundings on the hidden sample if we used the CAFEMIP prices instead of the original values. If the customer buying pattern remains the same, we can expect these prices to continue to do a good job.
