## Sunday, July 15, 2012

### Carrying Optimal Change in Your Wallet

The Alternative COIN-OR
How much change should I carry in my wallet? How many pennies, nickels, dimes, and quarters? If I carry too much, my pockets feel heavy, and if i carry too little, then I don't have enough to cover transactions in my office cafeteria and have to expend a dollar bill (of negligible weight) that was intended for the high-calorie vending machine, and end up carrying a lot more change after the transaction. We assume that the transaction amounts are small enough so that credit-cards are not used.

The cowboy uses a horse to cross the street whereas the O.R person uses CPLEX for the same reason. Let's analyze some simple cases here using CPLEX.

Problem 1: Determining the optimal coin distribution for a given change request.
Given that we are required to provide exact change of value v, where v = 1, ..., 100, what is the optimal distribution of coins for each scenario such that:
a) The total number of coins is minimized
b) The total weight of coins is minimized

The US Mint website provides the following coin weights in grams and its corresponding value that is captured via the following piece of java code:

static String[] name = {"penny","nickel", "dime", "quarter"};
static double[] weight = {2.500, 5.000, 2.268, 5.670};
static double[] value = {1., 5., 10., 25.};

As we can see by comparing their "bang to buck" ratios, the nickel is quite inefficient whereas the dime and quarter do pretty well. Therefore, one would expect the solution to carry more dimes and quarters, and fewer nickels and 'unscalable' pennies.  Furthermore, given that the b2b function is kinda non-convex, it's a good idea to solve these problems as discrete optimization models.

The optimal  (min count) vector of integer coin quantities (x) for a given input desired value = 'v' is determined using CPLEX-Java via the following integer knapsack model:

 value count weight penny nickel dime quarter 1 1 2.5 1 0 0 0 2 2 5 2 0 0 0 3 3 7.5 3 0 0 0 4 4 10 4 0 0 0 5 1 5 0 1 0 0 6 2 7.5 1 1 0 0 7 3 10 2 1 0 0 8 4 12.5 3 1 0 0 9 5 15 4 1 0 0 10 1 2.268 0 0 1 0 11 2 4.768 1 0 1 0 12 3 7.268 2 0 1 0 13 4 9.768 3 0 1 0 14 5 12.268 4 0 1 0 15 2 7.268 0 1 1 0 16 3 9.768 1 1 1 0 17 4 12.268 2 1 1 0 18 5 14.768 3 1 1 0 19 6 17.268 4 1 1 0 20 2 4.536 0 0 2 0 21 3 7.036 1 0 2 0 22 4 9.536 2 0 2 0 23 5 12.036 3 0 2 0 24 6 14.536 4 0 2 0 25 1 5.67 0 0 0 1 26 2 8.17 1 0 0 1 27 3 10.67 2 0 0 1 28 4 13.17 3 0 0 1 29 5 15.67 4 0 0 1 30 2 10.67 0 1 0 1 31 3 13.17 1 1 0 1 32 4 15.67 2 1 0 1 33 5 18.17 3 1 0 1 34 6 20.67 4 1 0 1 35 2 7.938 0 0 1 1 36 3 10.438 1 0 1 1 37 4 12.938 2 0 1 1 38 5 15.438 3 0 1 1 39 6 17.938 4 0 1 1 40 3 12.938 0 1 1 1 41 4 15.438 1 1 1 1 42 5 17.938 2 1 1 1 43 6 20.438 3 1 1 1 44 7 22.938 4 1 1 1 45 3 10.206 0 0 2 1 46 4 12.706 1 0 2 1 47 5 15.206 2 0 2 1 48 6 17.706 3 0 2 1 49 7 20.206 4 0 2 1 50 2 11.34 0 0 0 2 51 3 13.84 1 0 0 2 52 4 16.34 2 0 0 2 53 5 18.84 3 0 0 2 54 6 21.34 4 0 0 2 55 3 16.34 0 1 0 2 56 4 18.84 1 1 0 2 57 5 21.34 2 1 0 2 58 6 23.84 3 1 0 2 59 7 26.34 4 1 0 2 60 3 13.608 0 0 1 2 61 4 16.108 1 0 1 2 62 5 18.608 2 0 1 2 63 6 21.108 3 0 1 2 64 7 23.608 4 0 1 2 65 4 18.608 0 1 1 2 66 5 21.108 1 1 1 2 67 6 23.608 2 1 1 2 68 7 26.108 3 1 1 2 69 8 28.608 4 1 1 2 70 4 15.876 0 0 2 2 71 5 18.376 1 0 2 2 72 6 20.876 2 0 2 2 73 7 23.376 3 0 2 2 74 8 25.876 4 0 2 2 75 3 17.01 0 0 0 3 76 4 19.51 1 0 0 3 77 5 22.01 2 0 0 3 78 6 24.51 3 0 0 3 79 7 27.01 4 0 0 3 80 4 22.01 0 1 0 3 81 5 24.51 1 1 0 3 82 6 27.01 2 1 0 3 83 7 29.51 3 1 0 3 84 8 32.01 4 1 0 3 85 4 19.278 0 0 1 3 86 5 21.778 1 0 1 3 87 6 24.278 2 0 1 3 88 7 26.778 3 0 1 3 89 8 29.278 4 0 1 3 90 5 24.278 0 1 1 3 91 6 26.778 1 1 1 3 92 7 29.278 2 1 1 3 93 8 31.778 3 1 1 3 94 9 34.278 4 1 1 3 95 5 21.546 0 0 2 3 96 6 24.046 1 0 2 3 97 7 26.546 2 0 2 3 98 8 29.046 3 0 2 3 99 9 31.546 4 0 2 3 100 4 22.68 0 0 0 4

b) The minimum weight solutions are generated via:

 value count weight penny nickel dime quarter 1 1 2.5 1 0 0 0 2 2 5 2 0 0 0 3 3 7.5 3 0 0 0 4 4 10 4 0 0 0 5 1 5 0 1 0 0 6 2 7.5 1 1 0 0 7 3 10 2 1 0 0 8 4 12.5 3 1 0 0 9 5 15 4 1 0 0 10 1 2.268 0 0 1 0 11 2 4.768 1 0 1 0 12 3 7.268 2 0 1 0 13 4 9.768 3 0 1 0 14 5 12.268 4 0 1 0 15 2 7.268 0 1 1 0 16 3 9.768 1 1 1 0 17 4 12.268 2 1 1 0 18 5 14.768 3 1 1 0 19 6 17.268 4 1 1 0 20 2 4.536 0 0 2 0 21 3 7.036 1 0 2 0 22 3 9.536 2 0 2 0 23 5 12.036 3 0 2 0 24 6 14.536 4 0 2 0 25 1 5.67 0 0 0 1 26 2 8.17 1 0 0 1 27 3 10.67 2 0 0 1 28 4 13.17 3 0 0 1 29 5 15.67 4 0 0 1 30 2 10.67 0 1 0 1 31 2 13.17 1 1 0 1 32 4 15.67 2 1 0 1 33 4 18.17 3 1 0 1 34 5 20.67 4 1 0 1 35 2 7.938 0 0 1 1 36 3 10.438 1 0 1 1 37 4 12.938 2 0 1 1 38 5 15.438 3 0 1 1 39 6 17.938 4 0 1 1 40 3 12.938 0 1 1 1 41 4 15.438 1 1 1 1 42 5 17.938 2 1 1 1 43 6 20.438 3 1 1 1 44 7 22.938 4 1 1 1 45 3 10.206 0 0 2 1 46 4 12.706 1 0 2 1 47 4 15.206 2 0 2 1 48 6 17.706 3 0 2 1 49 7 20.206 4 0 2 1 50 2 11.34 0 0 0 2 51 3 13.84 1 0 0 2 52 4 16.34 2 0 0 2 53 5 18.84 3 0 0 2 54 6 21.34 4 0 0 2 55 3 16.34 0 1 0 2 56 3 18.84 1 1 0 2 57 5 21.34 2 1 0 2 58 5 23.84 3 1 0 2 59 7 26.34 4 1 0 2 60 3 13.608 0 0 1 2 61 4 16.108 1 0 1 2 62 4 18.608 2 0 1 2 63 6 21.108 3 0 1 2 64 7 23.608 4 0 1 2 65 4 18.608 0 1 1 2 66 4 21.108 1 1 1 2 67 6 23.608 2 1 1 2 68 7 26.108 3 1 1 2 69 8 28.608 4 1 1 2 70 4 15.876 0 0 2 2 71 5 18.376 1 0 2 2 72 5 20.876 2 0 2 2 73 7 23.376 3 0 2 2 74 8 25.876 4 0 2 2 75 3 17.01 0 0 0 3 76 6 23.376 1 1 2 2 77 4 22.01 2 0 0 3 78 6 24.51 3 0 0 3 79 9 30.876 4 1 2 2 80 4 22.01 0 1 0 3 81 5 24.51 1 1 0 3 82 6 27.01 2 1 0 3 83 7 29.51 3 1 0 3 84 8 32.01 4 1 0 3 85 4 19.278 0 0 1 3 86 5 21.778 1 0 1 3 87 6 24.278 2 0 1 3 88 7 26.778 3 0 1 3 89 8 29.278 4 0 1 3 90 5 24.278 0 1 1 3 91 6 26.778 1 1 1 3 92 7 29.278 2 1 1 3 93 8 31.778 3 1 1 3 94 9 34.278 4 1 1 3 95 5 21.546 0 0 2 3 96 5 24.046 1 0 2 3 97 7 26.546 2 0 2 3 98 8 29.046 3 0 2 3 99 9 31.546 4 0 2 3 100 6 26.546 0 1 2 3

The answers are different in many instances. For example, to generate 34 cents, the minimum count solution uses 6 coins including a nickel, whereas the min-weight solution is 4 grams lighter and uses 4 pennies and 3 dimes.
MC:    34    6    20.67    4    1    0    1
MW:   34    7    16.804  4    0    3    0

Problem 2: Assuming that each desired value scenario 'v' is equally likely to occur, find an optimal distribution of coins to carry such that we can exactly satisfy each scenario.

We can model this by creating a vector of 'x' used for each desired scenario, as well as a single integer vector 'z' such that any 'x' value for a scenario is no more than its corresponding 'z'.

for(int i = 0; i < numCoinTypes;i++){
}

CPLEX log:
Tried aggregator 2 times.
MIP Presolve eliminated 45 rows and 41 columns.
MIP Presolve modified 4 coefficients.
Aggregator did 5 substitutions.
Reduced MIP has 450 rows, 358 columns, and 1067 nonzeros.
Reduced MIP has 40 binaries, 318 generals, 0 SOSs, and 0 indicators.
Probing fixed 0 vars, tightened 8 bounds.
Probing time =    0.00 sec.
Tried aggregator 1 time.
Presolve time =    0.00 sec.
Found feasible solution after 0.00 sec.  Objective = 395.3600
Probing time =    0.00 sec.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 4 threads.
Root relaxation solution time =    0.02 sec.

Nodes                                         Cuts/
Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap

*    21     5      integral     0       36.5460       36.5460      969    0.00%

Thus, if we carry 10 coins (weighing ~36.5 grams) as distributed below:
penny:    4
nickel:    1
dime:      2
quarter:  3

we will be able to provide exact change for any scenario.

Problem 3: Determine the best 9, 8, 7, ..., coins to carry to minimize average expected absolute deviation from the desired values over all scenarios. Some of these turned out to be tough to solve to optimality due to the naive formulations employed. Nevertheless, optimal or near-optimal solutions were obtained in all instances.

Result: the optimal solution for n = 9, 8, 7, and 6 coins simply deletes a penny from (n+1) coin solution.
n =5, we delete a dime (0, 1, 1, 3)
n = 4, we delete a nickel (0, 0, 1, 3)
n = 3, 2, 1, are all-quarter solutions

Inventory Optimization
To more correctly model the residual change constraint (approximated via the objective function in Problem 3), suppose we are short by value 'delta': We can expend a dollar bill and end up with a net change of (100 - delta). In other words, we have to solve an inventory problem that for example, determines the optimal initial coin inventory vector 'z' such that the total weight of the expected final inventory after giving and/or receiving change over all scenarios  (and over multiple transactions or periods) is minimized. This model can be built by introducing a binary variable 'w' for each scenario to represent the case where a dollar bill is used or not used to supplement the value associated with 'z'. However, we do not know apriori, the distribution of the returned change, so some approximations are required. The analysis of this problem is a post for another day.

Read part-2 here, and part-3 here.