Optimizing Your Airport Baggage Claim Experience

You rub your weary eyes and get off that Airbus 380 to signal the end of your long 16-hour flight and wearily make your way to the baggage claim. You patiently wait along with your family to pick up your 4-6 pieces of check-in luggage before proceeding through the customs and immigration checks. It's a tiresome and time consuming process. Is there a way you can make things better for yourself? Perhaps...

Decision Problem
What is the most strategic location along the snake-like baggage claim conveyor belt to position oneself?
First, here's a sample picture of the baggage claim area (in the new Bangalore International Airport in India. source: inmagine.com)

Data
The one in the picture above looks like a standard belt with a single 'U' bend. To support passengers disembarking from an A-380, perhaps a longer belt having more than one 'U' may be required. Let us label each element of data we come across. Most of the data that we sift through below may not be needed, but it may be handy for other related analysis in the future.



As a first approximation, we simplify the topography by stretching out the belt in a straight line along one dimension. We thus have a simple chain-link graph having a single origin ('o') and destination node ('d'), and total o-d path length 'L'. Furthermore, 'd' is reconnected back to 'o' to create a cyclical network (and a circulation system, and a queuing system, and a multicommodity flow network). Let the average length of each bag be 'w'. We assume that the bags move at a constant velocity 'v', even though the value of 'v' itself may drop if the belt is heavily loaded (e.g. v = 0, if somebody checked in an elephant). Let the total supply (inventory) of bags that is to be circulated through the conveyor belt be 'N'. For simplicity, we assume that each passenger has checked in one bag and line up along the belt to pick up their bag if they manage to ID it in a timely manner. Flow through this simple network stops after a certain number of cycles have been completed (we could ignore this rule for simplicity), or after the inventory is depleted to zero, whichever occurs first. We assume that the supply at 'o' is replenished periodically as the baggage trucks roll in, every 'k' cycles, until all inventory has been offloaded.

Analysis
The number of bags displayable on the belt at any time is bounded by n = L/w, where typically n << N. The density (defined as bags per unit length) is a non-increasing function of the distance from 'o' at all times, since bags can only be removed from the belt between 'o' and 'd'. In other words, the 'n' bags are not distributed uniformly, and the density is maximum near 'o', and at a minimum near 'd'. A person nearest 'o' will have to scan a lot more bags on the average before a successful match - and due to the recycling of unmatched supply, he may end up scanning some bags more than once. (Perhaps the expected number of scans can be calculated using the above data, but I suspect simulation may be an easier alternative.) On the other hand, the person waiting nearest 'd' has the least amount of work to do, since every successful match upstream means one less failed scan for her. In the extreme case, if every other passenger correctly identified their own bag the first time they see it, the person at 'd' would have to do zero work. The first bag that would show up in front of her would be hers and she can simply pick it up.

Recommendation
If the objective is to least strain your already tired eyes, perhaps it's best that you wait near 'd'.

However, we often see people get off a plane and head right for 'o'. From a safety perspective, the bags belonging to people waiting near 'o' are likely to traverse the belt the least, minimizing the chances of a bag being mistakenly matched or stolen. From a security perspective, waiting near 'o' makes sense. It seems some airports now check luggage tags before allowing a passenger to exit the baggage claim area, so this safety objective may not be useful for long. There are other obvious considerations such as picking a spot that is least crowded.  If we assume that the probability 'p' that a passenger identifies their own bag in a timely manner is inversely related to the passenger density in their neighborhood and bag density, a primary consideration may be to just find a sparsely populated spot. Among such sparse spots, the one closer to 'd' may be a better option. On the other hand, the expected benefit from such a policy diminishes if too many passengers choose to be close to 'd', resulting in congestion. Finally, the state of the system changes over time. As the inventory depletes and passengers randomly exit the system, it may be worth relocating if you have the energy to do it.

All this stuff is useful provided your airline has not misplaced your bags in the first place.

FDI in Indian Retail: Good or Bad for India? In 100 Words or Less

Is building a hospital in an Indian town good? sure
If congress workers construct it? no.

Building a road generally a good idea? yes.
If the congress party supervises? nope.


Whether 'FDI* in retail' is bad or good strategy for India is moot. If its execution is mangled, it will end up being a horrific loss. A 60+ year trail of evidence supports this indictment of the Congress party.

"Amateurs Talk about Strategy, Dilettantes Talk about Tactics, and Professionals Talk about Logistics". The original quote is usually attributed to General Omar. Bradley, the "People's General".

(FDI = Foreign Direct Investment. 'FDI in Retail' may well be the proverbial straw the breaks the ruling Congress party's back.)

Visiting the Land of the Ramayana

India is timeless. Returning from there is always the difficult part and every trip to the land of the Ramayana and the Mahabharata invariably feels too short, and the most recent visit to South India was no exception.

India frustrates. Six decades of Soviet-style centralized planning after two centuries of looting by the British has wrecked the post-independence economy and sapped much of it's optimism. Economic liberalization introduced in the 1990s to rescue the economy has now slowed down. India is living proof that populist socialism works wonderfully in theory, but in practice brutally extinguishes the hopes and lives of millions. I have had first hand experience. India's first and foremost modern ORMS and analytics practitioner, P. C. Mahalanobis constructed large-scale linear programming models in the 1950s to optimize such grand centralized planning goals - an exercise in futility and certainly not the science and practice of 'better'!

(pic source: www.famousscientists.org)
Incidentally, one of the members of today's NAC (national advisory council), an unaccountable group of secretive leftist planners that work totally outside the purview of the Indian parliament, is Jean Dreze, a naturalized Indian citizen from Belgium who appears to have learned the art of coming up with equally grand centralized planning models (for the 21st century) from his father, who was both an operations researcher and economist. Not surprisingly, these grand schemes have failed miserably during human testing. It seems the modeling assumptions did not account for reality.

Mahalanobis did however leave behind a positive legacy. He founded the Indian Statistical Institute that produces many smart ORMS and statistics graduates to this day. He was a contemporary of the legendary Srinivasa Ramanujan and there is a well-recorded story of PCM posing a math problem to the young math genius from Tamil Nadu, who while cooking, answered the question and also provided a solution to the more general case.
 
Perhaps a major reason why India still has above-average GDP growth is the natural entrepreneurial spirit of its talented people that simply refuses to die. There is a market for everything in India.

India enchants. By the time I wake up in the morning in my ancestral village in the temple state of Tamil Nadu, my mother has created her Kolam (Rangoli) patterns in front of the house.

(pic source: /farm3.staticflickr.com)
In the old days, the designs were done using rice flour, so the little ants could feed on it. According to Indian belief, all living creatures, big or small, have souls just like humans. I doubt if my mother bothered to check if the Kolam path she traced every morning for the last 40 years was a Hamiltonian circuit or not ...

(pic source: 3.bp.blogspot.com)


India challenges. We board a train from Bangalore to Chennai. The seats are numbered sequentially but the ticket does not provide a deterministic clue on whether we have an aisle or middle seat. My family has contiguous seat numbers, but we soon discover that the seats themselves are not. A sole traveler shifting away from his window seat would have solved the problem in a jiffy but he refuses to oblige. We discover two other families facing the same problem. We perform an elegant three-way swap that would have made Lin and Kernighan proud, and enjoy a global optimal solution to this combinatorial problem for the remainder of the journey. It's about time the Indian Railways switches to alphanumeric seat labels.

India corrupts. I notice the beginnings of a flyover (overpass) in my village-town. Clearly there doesn't seem to be a need for it since the benefit/cost ratio seemed rather poor, but the politicians wanted one, so the town has to endure it. They're also widening the train tracks that go thru the town, which actually appears to be a sane idea. However, they want to rebuild a working bridge to accommodate this change. The crazy guys try to demolish the old bridge, but it proves to be too strong, so work is delayed. Eventually the new one will come up and will most likely be built with sub-standard building material.

India heals. I visit the temple of my Ishta Devta (approximately translates to: 'preferred iconic embodiment of the divine') that is located on a hill in Pazhani,Tamil Nadu. In the past, many fervently monotheist invaders of India mistook this sophisticated Indian concept for "idol worship", leading to genocide and wholesale temple destruction. sigh.

(pic source: upload.wikimedia.org)

I visit this famous temple the traditional way by climbing the many hundred steps to the summit. It's also a great morning work out. My family choose the popular modern mode of transportation and take the cable-car and arrive 30 minutes later! There appears to be a classical circulation problem hidden there.

(pic source: commondatastorage.googleapis.com)
The temple staff appear to be practicing some form of revenue management while also maximizing cable car capacity utilization. Uphill rides are twice as expensive as riding down, off-peak rides are half-price, and they wait until the cars are at capacity before launching. Hence the delay. Once inside the temple complex on the top, the administrators appear to employ 'lot sizing' where people line up and then ushered in to view the Murthi (icon) of the deity in batches that seem to be somewhat synchronized with cable car arrivals at the top. Thus I derive no significant advantage in getting to the top earlier than the cable-car riders. You either wait at the bottom of the hill or on top and the total time spent in the system is practically constant.

India beckons. All said and done, I cant wait to get back. Until then, here's an audio sample of South Indian classical (Carnatic) vocal synced to Western instrumental music.

Optimal Location of Speed Limit Signs

One of the nice things about the relatively more recent automobile GPS products is that they are able to inform us of the current speed limit. Sometimes, when we take our eyes of the road for a second to grab a soda, we may have driven past a speed limit sign and be unaware of the new speed limit. Of course, there are times when the GPS unit itself does not display the speed limit for certain areas, and at other times, it is off by 10 mph, perhaps due to recent road updates. Like any decision support system, the GPS unit cannot be a fail-safe backup for user negligence.

The problem of optimally locating speed limit signs on a network must have been studied and solved a long time ago especially since the analysis of traffic and transportation networks has long been popular research area among ORMS folks. Perhaps there exists a practical combinatorial optimization problem in terms of determining minimal/safest/least ambiguous ways of locating speed signs in the presence of scarce resources and budget limits. A partial list of assumptions and constraints include:
- Speed limits change in discrete quantities of 5mph or 10 mph
- Every driver will treat the last speed limit sign (or update) they saw on the network as the prevailing speed limit
- Every driver at every point in the road network must be in unanimous agreement on what the speed limit is. This is the ideal situation.
- In practice, perhaps the above requirement can be relaxed to stipulate that any non-trivial ambiguity must be resolved with a certain time or distance threshold whose value is location-specific
- Different types of speed limit signs are possible - they may be time-dependent (day/night) as well as location-dependent (school, bridge, tunnel) - Speed limit values can be fixed or variable ("smart roads"). This requirement can potentially inject a dynamic optimization aspect into the problem.

Perhaps a greedy method may be sufficient to generate a good answer to the (fixed value) speed-limit signpost location problem. There are of course, numerous other related location optimization problems on road networks:
locating advertisement hoardings, direction/information signs, emergency vehicles, detours, etc. All these models appear to be well studied in the literature. The proliferation of smart-phones can also have an impact on future 'smart road network' design in general. All in all, location, location, location science continues to be a very interesting sub-area of Operations Research.

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.

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$.

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.

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.