Sunday, July 22, 2012

Ekthetikophobia: The Fear of the Exponential

More specifically, the fear of having to solve an NP-Hard optimization problem to save your job. 

Do you or anyone else in your organization exhibit symptoms of Ekthetikophobia?

Sample Responses by Ekthetikophobes
1. Resign: Capitulation is by far the most common response, especially if the person does not have an ORMS background and is oblivious to the 'science of better'. Throw hands in the air, lose faith in humanity, and slurp spoonfuls of the nearest meta-heuristic algorithmic prescription provided by bees, ants, bacteria, squeaky wheels, mutant turtles, ... any nature cure that uses pseudo random numbers. This response is best captured by the Hindi proverb "Naach Na Jaane, Aaangan Teda",i.e., a bad dancer blames the uneven floor.

2. Controlled Panic. This is pretty typical of a generation of OR practitioners weaned on CPLEX. Like MDs trying to decode a deadly new strain of flu, the overriding urge is to throw money at the problem by ordering the latest versions of the baddest bunch of industrial strength optimization solvers in the market with matching supercomputing accessories to run massive benchmarks, and generally scare the pants off their IT managers who work with depression-era budgets.

3. Code. This is relatively more common to programming gurus and follows exactly one rule: If you throw sufficiently well-written code at any problem, it must work. This is so crazy, these guys are on to something here.

4. Publish. The median response from E.phobic research folks is to put this exhibit on a pedestal for everybody to gaze at. It's akin to a biologist discovering a new specie or an astronomer sighting a new planet that shouldn't have been there. Half of these people (surely OR types) will go on to demonstrate the monstrosity of this new problem based on diabolical worst case instances that even a God who plays dice would not inflict on mankind. The other, more elegant half (theoretical CS E.phobes) propose 'factor of 2' approximations that cover all remaining difficult instances missed by the Muggles, yet just as useful practically, before declaring victory. Then over the next two decades: keep shaving of that factor; rinse & repeat; it's a veritable cottage industry.

Exaggerations aside, ranked at the top of the most systematic, resourceful, innovative, and practically useful responses toward 'new' NP-Hard optimization problems must be the approach adopted by Dantzig, Fulkerson, and Johnson (1954) to tackle a 49-city Traveling Salesman Problem using 1950s computing technology and fearless minds that dared lasso the exponential.

July 22: minor fix: added missing text.

Thursday, July 19, 2012

Predicting the Value of a Bunch of Coins

This is the last part of the 'Coin trilogy'. Here's part-1 and part-2. In this post, we attempt to answer questions on predicting the value for a bunch of coins for which we only know its weight but not the exact internal distribution among coin types.

If somebody gave you the option of choosing either the value of a kilo of coins or 40$, which will you pick?
Using CPLEX, we determine that the maximum possible value for 1000 grams of pennies, nickels, dimes, and quarters is 44.05$, so if you took the 40$, there is a small chance you will incur a loss. If the bag was packed with 400 pennies (weighs exactly a kilo), you'll make a 36$ profit. If the coins types were uniformly distributed, its value would be about 26$, and you would make a 14$ profit.

Say you believe you have 100$ worth of coins in a jar that you want to cash out at a Coinstar machine. How much would that weigh? A lower bound for that answer is 2.268 Kilos. If the coin types were uniformly distributed in the jar, you would carry about 3.7 Kilos.

What kind of coin ratios does a vending machine carry? This online post author made enough purchases to empty out a vending machine and found this:
Quarters:Dimes:Nickels in the ratio 1:2:1.175

Assuming that the vending machine has to satisfy exact change for any value between 5c and 95c in 5c increments, a minimum weight solution is:
Nickels:1, Dimes:9 (10 coins, weight 25.412g) with zero quarters. However, by adding a secondary objective of also minimizing the number of coins (limited coin capacity?), we obtain the following alternative optimal solution that threw away 5 dimes and picked up 2 quarters:
Nickel:1, Dime:4, Quarter:2 (7 coins, 25.412g)

Quarters and Dimes are now present in the same ratio as that in the vending machine. However, our model doesn't like nickels much (although a melted nickel was once worth more than its value).


I have a digital counting jar that displays the current value of the coins currently in the jar. It currently reads $20.05, and its weight (excluding the empty jar) is about 700 grams. For this weight, the maximum value is 30.85$. If my coins were uniformly distributed in the jar, the model predicts a "maximum" value of 18.7$, which means that I have relatively more dimes and/or quarters in my mix. A dime and a nickel have the exact same bang-to-buck ratio, i.e. value/weight ratio, which is a source of the alternative optimal solutions discussed in part 2.

US Mint Production
Averaged over 2010-2011, the coins are produced in the approximate ratio:
p:n:d:q
12:1.5:3.5:1


Quite different from our preferred ratios calculated in part-1 and part-2. At this rate, my 700 gram jar would contain only about 15$ and a kilo of coins in this ratio would be worth about 18$.

Tuesday, July 17, 2012

Alternative Optimal Solutions to the Coin Mix Problem

The solution to the 'optimal change' problem analyzed in the previous post is further examined from a practice perspective. Again, we use CPLEX to do this since it is quite convenient for such analyses.

Problem 1 is an integer knapsack problem that is known to be theoretically NP-Hard but fairly easy to solve in practice using Dynamic Programming. For this specific coin instance, enumeration with simple pruning rules that exploit the problem structure would work too.

Globally Robust versus Scenario-Optimal
Problem 2 is relatively trickier. It attempts to minimize the maximum weight across the feasible solutions to each of the change scenarios. The value of the 10-coin min-weight solution in the previous post:
Pennies:Quarters:Dimes:Nickels::4:3:2:1 is slightly more than a dollar (1.04$). This coin mix will be able to satisfy any random change request in the range 1-100c. Note: If we only cared about change between 1-99c, an optimal solution (35.412g, 99c) is: PQDN::4241.
However, while an optimal solution to Problem 2 is robust in terms of this ability to meet any request, it is not necessarily optimal in terms of meeting specific coin requests. For example, if we only ever use change for a 3pm $1.68 cup of Starbucks in the cafeteria, then the 4-3-2-1 solution may not be the best. However, if by chance, we choose to downsize to a smaller $1.29 cup one day, then the 68c solution may not work.

First Among Equals
We only used a single goal within the optimization formulations: either min-sum, min-count, or min-weight. As mentioned in a recent post, practical optimization models almost never go into production carrying just a single goal. Consider these alternative optimal optimal solutions for 96c:

v   #     wt         p n d q
96 9    24.046    1 0 7 1
96 6    24.046    1 0 2 3

The second solution has the same weight but fewer quarters + dimes, and does the same job a little more efficiently. On the other hand, the first solution perhaps allows greater flexibility in terms of meeting other change requests (e.g. 30c, 40c).  

Continuing along this path,
a) if we set the lower bound on the number of dimes in Problem 2 = 7, we obtain the following 13-coin alternative to the 4-3-2-1 answer, having the same weight and value (36.546g, $1.04) PQDN::4171


b) If we want a least-value solution to Problem 2, then an optimal objective function value whose corresponding weight is only 1.5g more than the min-weight is 1.0$ (37.912g)
PQDN::5241 or PQDN::5091
(If you ever change a dollar bill in the future, do so in a robust manner via this mnemonic: PQDN 5241 :)


Interestingly, these 1$ solutions include five pennies (a feasible 4-penny solution has a value of 1.04$ or more).

Depending on the context, one of these solutions is more preferable than the others, and this preference can be quantified by suitably incorporating secondary and tertiary goals within the objective function. In contrast, a pure constraint satisfaction model will solely focus on generating feasible solutions ignoring any preference. These principles are the cornerstone of many mission-critical optimal planning systems and operational decision support applications deployed across industries.

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:

cplex.addMinimize(cplex.sum(x));
cplex.addEq(v, cplex.scalProd(value, x));

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:

cplex.addMinimize(cplex.scalProd(weight, x));
cplex.addEq(desiredValue, cplex.scalProd(value, x));


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.addLe(0., cplex.diff(z[i], x[desiredValue][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.