Category Archives: Promoting OR

How to Optimally Allocate “Bribe” Money

 As I sat through a 4-hour meeting the other day, I had an idea for a very useful and generic prescriptive analytics model to be used in conjunction with the results of a statistical learning study (e.g. a regression model). I can immediately see a large number of applications for this model, some of which I’ll illustrate in this post. I also believe this idea could be turned into an interesting case study (combining predictive and prescriptive analytics) for class discussion in a master’s level course (MBA or specialized MS), and I’d love to partner with someone to turn that into reality. Let me know if you’d like to pursue this! (Disclaimer: I don’t have much experience writing cases, but I want to get better at it.)

Without further ado…

You’re interested in gaining a better understanding of the likelihood, or probability p, that certain agents will perform a given action that benefits you. So you hire a group of business analytics consultants who create a statistical learning model M that predicts the value of p with high accuracy given an agent (and their attributes/characteristics) as input.

Those agents with high-enough probability of performing the action, say p \geq 50\% (a subjective choice), don’t concern you too much because they’re already on your side. Your focus is on those whose value of p is less than 50%. One of the outcomes of model M is a number for each agent (or group of similar agents) indicating how much of an effect giving that agent a financial incentive would have on the value of their action probability p. For example, this number could be 0.1 for a given agent, indicating that they’d be 10% more likely to perform the action for each $1000 of incentive they receive. So, assuming a linear model, if their originally predicted p were 35%, giving them $2000 would be enough to push them beyond your target 50% threshold. (Considering incentives are given in multiples of $1000.)

Before we go any further, let me make this more concrete with a few examples.

Example 1: You are the seller of a product. Agents are customers. The action is purchasing your product. The financial incentive is a discount. You have a budget for the overall discount you can give and you want to optimally allocate different discount amounts to different customers to bring as many of them as possible to the brink of buying your product (say, a 50% chance).

Example 2: You are a politician. Agents are voters. The action is voting for you. The financial incentive is a bribe. This happens in Brazil and likely in other countries as well. (Disclaimer: I’m not advocating that this is an ethical or moral thing to do. Like any superpower, however, mathematics can be used by the dark side as well.)

Example 3: You are a university. Agents are admitted students. The action is picking you to attend. The financial incentive is a scholarship.

I’m sure you can come up with other examples. Let me know in the comments!

So the big question is: How do we optimally allocate the limited pool of financial incentives? Optimization to the rescue! I’ll provide a link to an Excel spreadsheet below, but first let’s understand the math behind it.

Given n agents, for each agent i, let b_i be how much the agent’s action probability (before the incentive) is below my target threshold, and let c_i be how much agent i‘s action probability increases for each f dollars of financial incentive. In my example above, b_i=0.15 (50% minus 35%), c_i=0.1, and f=\$1000.

Let’s create two variables for each agent i. Variable x_i is an integer number indicating how many f-dollar incentives we decide to give to that agent. And variable y_i is a binary (yes/no) variable indicating whether or not we manage to bring agent i to our side (i.e. whether we raised his/her action probability beyond the threshold).

To indicate that our goal is to push as many agents beyond the action threshold as possible, we write

\displaystyle \max \sum_{i=1}^n y_i

If our total budget for financial incentives is B, we respect the budget with the following constraint (note that the sum of all x_i equals the total number off-dollar financial incentive packages given away):

\displaystyle f \sum_{i=1}^n x_i \leq B

Then, if we want y_i to be equal to 1 (meaning “yes”), we need x_i to be high enough for the increase in the agent’s action probability to exceed the threshold value. This can be accomplished with these constraints

\displaystyle b_i y_i \leq c_i x_i

In my earlier example, the above constraint would read

\displaystyle 0.15 y_i \leq 0.1 x_i

Therefore, unless x_i is at least 2, the value of y_i cannot be equal to 1.

That’s it! We are done with the math. Wasn’t that beautiful?

Here’s an Excel spreadsheet that implements this model for a random instance of this problem with 20 agents. It’s already set up with all you need to run the Solver add-in. Feel free to play with it and let me know if you have any questions.

Advertisements

1 Comment

Filed under Analytics, Applications, Integer Programming, Mathematical Programming, Modeling, Motivation, Promoting OR, Teaching

Theory versus Practice, Intangibles, Intuition, and the Usefulness of Imperfection

I felt like putting in writing a few thoughts I often find myself telling my students, and hence this post. You can download a (nicer) PDF version of it here.

Theory versus Practice: A Challenge

It was a rainy Saturday afternoon…

“Ready? Go!”

As she reached for her pencil and began scribbling, I opened an empty Excel spreadsheet and started typing in the data and thinking out loud.

“Eight integer variables, three constraints, plus lower and upper bounds. How is it going over there?”

“I’m doing OK. Let me think.”

A minute later, I click “Solve” and declare victory.

“There you go: $2.80. Can’t beat that!”

“Five buns? Do you expect people to eat a burger with five buns?”

“Hmm…you’re right. One more constraint… voilà $2.62. The best burger on the market! What did you get?”

“Mine costs $2.61.”

“I win! Ha, ha!”

“But look at your burger! Nobody would ever want to eat this crap. Mine is much more appetizing.”

As I reluctantly examined the two solutions, there was no denying the obvious.

That was me and my wife solving the Good Burger puzzle. The challenge is to create the most expensive burger out of a given set of ingredients such as beef patties, cheese, lettuce, tomato, etc., while keeping sodium, fat, and calorie counts in check. Her hand-calculated solution was suboptimal by one cent. It was technically worse than mine, but what does optimality really mean in practice?

Optimality or Bust?

Once upon a time, at the board meeting of a for-profit company…

“Today, I’m excited to report the results from the cost-cutting initiative that my team of analytics experts developed over the last six months. We managed to produce a solution to our problem that improves profits by 6%.”

“But is this solution optimal?”

Said no one ever after hearing “improves profits by 6%.”

Intangibles and Intuition

The two anecdotes above illustrate an important idea that I emphatically stress to my students every spring semester: models aren’t perfect, and that’s perfectly OK. There’s a reason why business analytics is known as “the science of better” rather than “the science of provably optimal.” More often than not, it is impossible to capture all nuances of a real-life problem into a mathematical model. Therefore, solutions produced by such a model are to be taken with a grain of salt and cautious optimism. Do these numbers still make sense after the omitted intangibles are brought back into the picture? If so, great. If not, can we slightly modify the solution? Do we need to revise the model? When building my burger, I ignored flavor considerations and overall gastronomic appeal, whereas my wife didn’t.

Another matter with which non-experts struggle is keeping their intuition from negatively affecting their modeling choices. Or, as I like to say in class, “don’t try to solve the problem; focus on representing the problem.” A mathematical model is a translation, say, from English to formulas, of the story that warrants investigation. Letting your understanding of the story bias you into thinking the solution should/shouldn’t look a certain way, and adding that assumption into your model, can be detrimental. As humans, we tend to think intuitively, which in turn limits the universe of possibilities we look at. Good solutions to complex problems can be, at least at first sight, counterintuitive. Make sure your model has the freedom to consider “weird” courses of action as well.

The Usefulness of Imperfection

Imperfect models create imperfect solutions that can still be useful. Having a solution in the ballpark of good answers is better than looking at a blank slate and not knowing where to begin. Solving a model many times with a range of input values improves your understanding of how certain numbers relate to others. As your understanding of the problem improves, that (initially) counterintuitive solution starts to make sense. Improved understanding leads to revising your initial assumptions and even realizing that what you thought mattered is secondary. What really matters is this other number to which you didn’t pay much attention to begin with. In extreme cases, this first model may lead you to conclude that you need to create a completely different model to solve a completely different problem, and that’s OK too! You are learning about your problem in the process of trying to solve your problem. Finally, it may very well be that your problem, as originally stated, has no solution. This would have been difficult to detect by hand because complex problems have several moving parts with intricate relationships of cause and effect. Having a model whose output says “infeasible” can be a valuable tool in a meeting. It is concrete proof that the original question and/or assumptions are inconsistent in some way. (Assuming there’s no mistake in the model, of course.) From there, it will be a much shorter path to convincing people to revise the question/assumptions than it would have been otherwise. Who would have thought? Modeling also makes your meetings more efficient!

1 Comment

Filed under Analytics, Modeling, Promoting OR, Teaching, Tips and Tricks

Buying Metrorail Tickets in Miami

(Credits: Thanks to my MBA student Mike Plytynski for the idea for this post.)

Instead of a subway system, Miami has surface trains like the one depicted below. This is known as our Metrorail system. The Metrorail connects to the Tri-Rail system (which takes you north as far as West Palm Beach) and also to the free-to-ride, fully-automated, electrically-powered Metromover.

If you are a (reasonably) frequent Metrorail rider, you may consider buying a rechargeable card at one of the ticket vending machines. There is a 1-day pass ($5.65), a 7-day pass ($29.25), and a monthly pass ($112.50) that offer unlimited rides, but let’s focus on the case when you don’t ride often enough to justify the cost of such passes.

The current cost of a one-way trip is $2.25, regardless of distance traveled. The vending machines at the entrance of each Metrorail station allow you to load the following pre-specified amounts onto your card: $1, $2.25, $3, $4.50, $5, $10, $20, and $40.

No one likes to waste time having to stop by the vending machine to reload the Metrorail card. Besides, by Murphy’s Law, the next train will arrive and depart exactly when you’re stuck in line at the machine trying to reload your card. Therefore, we’ll consider that our objective is to minimize the number of visits to the vending machine to load our card with enough money for n one-way trips. If we were free to load any amount on the card, we could simply load n times $2.25 and be done. The absence of this flexibility is what makes this situation both interesting and a reason for us to hate the Metrorail. So let’s write an optimization model to solve this problem.

Let variable x_1 be the number of times we go to the vending machine to load $1 on the card. Let x_2 be the number of times we load $2.25 on the card, and so on all the way to x_8 (how many times we load $40). To minimize the number of visits to the vending machine, we write the objective function

\min x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8

To make sure we load enough money on the card for n trips, we write the constraint

x_1 + 2.25x_2 + 3x_3 + 4.5x_4 + 5x_5 + 10x_6 + 20x_7 + 40x_8 \geq 2.25n

If we are not careful, we may end up with unnecessarily too much money left on the card. So it’s wise to limit that excess with the constraint

x_1 + 2.25x_2 + 3x_3 + 4.5x_4 + 5x_5 + 10x_6 + 20x_7 + 40x_8 - 2.25n \leq L

where L is a limit on what we’d be willing to have left on the card after the n trips are completed. Conceivably, this leftover amount could be applied toward your next batch of n trips. Hold that thought; we’ll return to it later.

I put together an Excel Solver spreadsheet model for this problem, which you can download from here (sheet named “standard” in the Excel file).

If you change the second constraint above to an equality and solve this problem for different values of n and L, you can create the following heat map. The numbers in the colored squares indicate the minimum number of required visits to the vending machine.

Interestingly, some values of n, such as 10, 18, and 20, are more friendly in the sense that they allow you to visit the machine at most twice while incurring a small leftover amount (no more than $0.50). On the other hand, to avoid visiting the machine more than twice when paying for 12, 14, or 16 trips, you must be willing to accept a much higher ending balance: $3, $8.50, and $4, respectively. In addition, some of the reload amounts that might at first seem useless, such as $5 and $10, actually do get used in the optimal solutions for some values of n and L.

Ending Balances As Multiples of $2.25

As we saw above, allowing for larger ending balances on the card can help reduce the number of visits to the vending machine. One way to make these balances useful is to apply them toward future trips. If the balance is a multiple of the cost of a one-way trip, even better. To do that, we can replace the second constraint above with

x_1 + 2.25x_2 + 3x_3 + 4.5x_4 + 5x_5 + 10x_6 + 20x_7 + 40x_8 - 2.25n = 2.25k

where k is a new, non-negative integer variable. The sheet called “leftover is multiple” in this Excel file implements this version of the optimization model. The conclusion is that you pretty much only need 2 visits to the vending machine for n \leq 20, and the value of k seems to decrease as n increases. (See Excel file for detailed results.)

Now, if only I could get someone from Miami-Dade Transit to read this post…

Leave a comment

Filed under Applications, Integer Programming, Knapsack, Mathematical Programming, Modeling, Motivation, Promoting OR, transportation

Bringing Research into the Classroom: Can Relevant and Impactful be Easy to Explain?

math-equation_chalkboard O.R. researchers and practitioners are constantly churning out papers that tackle a wide variety of important and hard-to-solve practical problems. On one hand, as a researcher, I understand how difficult these problems can be and how it’s often the case that fancy math and complex algorithms need to be used. On the other hand, as someone who teaches optimization to MBA students who aren’t easily excited by mathematics, I’m always looking for motivational examples that are both interesting and not too complex to be understood in 5 minutes. (That’s the little slot of time I reserve at the beginning of my lectures to go over an application before the lecture itself starts.)

Every now and then, I come across a paper that fits the bill perfectly: it addresses an important problem, produces impactful results, and (here comes the rare part), accomplishes the previous two goals by using math that my MBA students can follow 100%, while being confident that they themselves could replicate it given what they learned in my course (the optimization models).

The paper to which I’m referring has recently appeared in Operations Research (Articles in Advance, January 2017): The Impact of Linear Optimization on Promotion Planning, by Maxime C. Cohen, Ngai-Hang Zachary Leung, Kiran Panchamgam, Georgia Perakis, and Anthony Smith (http://dx.doi.org/10.1287/opre.2016.1573).

If I had to pick one word to describe this paper, it would be BEAUTIFUL.

I immediately proceeded to put together a 5-minute summary presentation (8 slides) to cover the problem, approach, and results. I’ll be showing this to 100 of my MBA students on this coming Tuesday (Valentine’s Day!). I hope they love it as much as I did. Feel free to show this presentation to your own students if you wish, and let me know how it went down in the comments.

A recent Poets & Quants article explains how business schools with the highest quality teaching strive to bring their faculty’s research into the classroom so that students get to learn the latest and greatest ideas. The O.R. paper above is a perfect example of when this can be done effectively.

Leave a comment

Filed under Analytics, Applications, Integer Programming, Linear Programming, Modeling, Motivation, Promoting OR, Research, Teaching

The First Sentence of the Great Analytics Novel

Thedarktower7 I’ve written many times before about the importance of promoting O.R. to the general public. One of the ideas that’s been suggested by several people is the possibility of writing a work of fiction whose main character (our hero) is an O.R./Analytics person. I still believe this is a great idea, if executed properly.

Today, my wife brought to my attention The Bulwer-Lytton Fiction Contest, which, according to their web page, consists of the following:

Since 1982 the English Department at San Jose State University has sponsored the Bulwer-Lytton Fiction Contest, a whimsical literary competition that challenges entrants to compose the opening sentence to the worst of all possible novels. The contest (hereafter referred to as the BLFC) was the brainchild (or Rosemary’s baby) of Professor Scott Rice, whose graduate school excavations unearthed the source of the line “It was a dark and stormy night.” Sentenced to write a seminar paper on a minor Victorian novelist, he chose the man with the funny hyphenated name, Edward George Bulwer-Lytton, who was best known for perpetrating The Last Days of PompeiiEugene AramRienziThe CaxtonsThe Coming Race, and – not least – Paul Clifford, whose famous opener has been plagiarized repeatedly by the cartoon beagle Snoopy. No less impressively, Lytton coined phrases that have become common parlance in our language: “the pen is mightier than the sword,” “the great unwashed,” and “the almighty dollar” (the latter from The Coming Race, now available from Broadview Press).

Just like an awful first sentence can be a good indicator of a terrible book, the converse can also be true. Take, for example, the first sentence of Stephen King’s The Dark Tower series, which I happen to be reading (and loving) as we speak:

The man in black fled across the desert, and the gunslinger followed.

It’s such a strong, mysterious, and captivating sentence…

…which brings me to the point of this post. If it’s going to be difficult to write The Great Analytics Novel, what if we start by thinking about what would be the perfect, most compelling sentence to start such a novel? Yes, I propose a contest. Let’s use our artistic abilities and suggest starting sentences. Feel free to add them as comments to this post. Who knows? Maybe someone will get inspired and start writing the novel.

Here’s mine:

Upon using the word “mathematical” he knew he had lost the battle for, despite the dramatic cost savings, their logical reasoning was instantly halted, like a snowshoe hare frozen in fear of its chief predator: the Canada lynx.

I can’t wait to read your submissions!

4 Comments

Filed under Analytics, Books, Challenge, INFORMS Public Information Committee, Motivation, Promoting OR

Promote O.R. by Taking Folks by Surprise

Due to a number of things that have been keeping me busy, including a 20-day fight against a kidney stone that is now finally over, I haven’t had much time to post. I have two ideas that I plan to turn into posts soon, but in the meantime I’d like to suggest that everyone write a post about “santa claus” and “reindeer” (and properly tag it with those words). As the picture below indicates, I’ve been getting a lot of hits lately (way above average) and, digging deeper, I see that my post entitled “How Should Santa Pair Up His Reindeer?” has had 2,209 views this past week. Yay for Christmas!

Screen Shot 2012-12-04 at 10.27.15 AMAs a matter of fact, I suggest that everyone write a post about each special date of the year (Easter, Fourth of July, Valentine’s Day, Summer Camp, etc.). Those will keep bringing you recurring visits, without any extra effort, year after year. Of course not all (in fact, most) of those visits will be here for O.R. But that’s the point! If we want to spread the word about O.R. we’ve got to take people by surprise. “I was just looking for a cute reindeer picture and this guy blew my mind by showing me that math and reindeer have something to do with each other! How cool is that!”

BTW, I just realized I do not have an Easter post. I need to take care of this…

Leave a comment

Filed under Holidays, Promoting OR

Did You See Any OR During Apple’s iPhone 5 Announcement? I did!

On September 12, Apple finally announced its much-awaited iPhone 5. I didn’t have time to watch the keynote speech, but I watched the shorter 7-minute video that’s posted on Apple’s web site featuring Jony Ive, Apple’s Senior Vice President, Design. In that video, at around the 5-minute, 26-second mark, something they said caught my attention: the way they put parts together during the assembly process. I encourage you to watch that part of the video before reading on.

Jony Ive says:

Never before, have we built a product with this extraordinary level of fit and finish. We’ve developed manufacturing processes that are our most complex and ambitious.

And on Apple’s web site, they say this:

During manufacturing, each iPhone 5 aluminum housing is photographed by two high-powered 29MP cameras. A machine then examines the images and compares them against 725 unique inlays to find the most precise match for every single iPhone.

So let’s see if I understood this correctly. In a typical manufacturing operation, the multiple parts that get put together to create a product are put together without much fuss. A machine makes part A, another machine makes part B, and perhaps a robotic arm or a third machine takes any one of the many part A’s that are coming down a conveyor belt and attaches it to any one of the many part B’s that are coming down another conveyor belt. What Apple did was to improve on the “any one” choice. I don’t know if Apple pioneered this idea, I’d say probably not, but this is the first time I hear about something like this. If you’ve seen this before, let me know in the comments.

Before OR comes into play, Computer Science does its job in the form of computer vision / image processing algorithms. The photographs of the parts are analyzed and (I’m guessing) a fitness score is calculated for every possible matching pair of parts A (the housing) and B (the inlay). What happens next? How do they pick the winning match? Here are some possibilities:

  1. Each part A is matched with the part B, among the 725 candidates, that produces the best matching score.
  2. A 725 by 725 matrix of fitness scores is created between 725 parts of type A and 725 parts of type B, and the best 725 matches are chosen so as to maximize the overall fitness score (i.e. the sum of the fitness scores of all the chosen matches).
  3. Proceed as in the previous case, but pick the 725 matches that maximize the minimum fitness score. That is, we worry about the worst case and don’t let the worst match be too bad when compared to the best match.

After these 725 pairs are put together, new sets of parts A and B come down the conveyor belt and the matching process is repeated. Possibility number 1 is the fastest (e.g. do a binary search, or build a priority queue), but not necessarily the best because every now and then a bad match will have to be made. Possibilities 2 (an assignment problem) and 3 (assignment problem with a max-min objective) are better, in my opinion, with the third one being my favorite. They are, however, more time consuming than possibility 1. Jony Ive says the choice is made “instantaneously”, which doesn’t preclude something fancier than possibility 1 from being used given the assignment problems are pretty small.

The result? In the words of Jony Ive:

The variances from product to product, we now measure in microns.

It is well-known that OR plays a very important role in manufacturing (facility layout, machine/job scheduling, etc.) but it’s not every day that people stop to think about what happens in a manufacturing plant. This highly-popular announcement being watched by so many people around the world painted a very clear picture of the kinds of problems high-tech manufacturing facilities face. I think it’s a great example of what OR can do, and how relevant it is to our companies and our lives.

Leave a comment

Filed under Applications, iPhone, Motivation, Promoting OR