Category Archives: Teaching

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

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

Portuguese Pronunciation and Language Tips

I’ll be taking a group of 34 MBA students on an international business immersion trip to my native Brazil this Spring. We’ll be visiting about a dozen companies in the cities of São Paulo and Rio de Janeiro. This is an initiative created by the awesome Center for International Business Education and Research (CIBER) at the University of Miami.

I’d like my students to be able to pronounce some of the main sounds in Portuguese correctly because I know Brazilians pay attention and really enjoy when foreigners make an effort to say things properly. Therefore, I created a video in which I go over what I consider to be some of the most important things to know when speaking Portuguese (there are others, but I didn’t want the video to be too long).

You can access it on my YouTube channel here: https://www.youtube.com/watch?v=LzgoYFokBPk

Moreover, the 2016 Olympic Games are coming, so I figured these tips could be useful for a larger audience as well. I wish American sports casters would watch this video because they murdered the pronunciation of everything during the World Cup in 2014.

Bonus material: My daughter, Lavinia Lilith, a.k.a. #LLCoolBaby, makes a short appearance at around the halfway mark.

Enjoy!

Leave a comment

Filed under Brazil, People, Teaching, Tips and Tricks, Travel, Videos, YouTube

Improving a Homework Problem from Ragsdale’s Textbook

UPDATE (1/15/2013): Cliff Ragsdale was kind enough to include the modification I describe below in the 7th edition of his book (it’s now problem 32 in Chapter 6). He even named a character after me! Thanks, Cliff!

When I teach the OR class to MBA students, I adopt Cliff Ragsdale’s textbook entitled “Spreadsheet Modeling and Decision Analysis“, which is now in its sixth edition. I like this book and I’m used to teaching with it. In addition, it has a large and diverse collection of interesting exercises/problems that I use both as homework problems and as inspiration for exam questions.

One of my favorite problems to assign as homework is problem number 30 in the Integer Linear Programming chapter (Chapter 6). (This number refers to the 6th edition of the book; in the 5th edition it’s problem number 29, and in the 4th edition it’s problem number 26.) Here’s the statement:

The emergency services coordinator of Clarke County is interested in locating the county’s two ambulances to maximize the number of residents that can be reached within four minutes in emergency situations. The county is divided into five regions, and the average times required to travel from one region to the next are summarized in the following table:

The population in regions 1, 2, 3, 4, and 5 are estimated as 45,000,  65,000,  28,000,  52,000, and 43,000, respectively. In which two regions should the ambulances be placed?

I love this problem. It exercises important concepts and unearths many misconceptions. It’s challenging, but not impossible, and it forces students to think about connecting distinct—albeit related—sets of variables; a common omission in models created by novice modelers. BUT, in its present form, in my humble opinion, it falls short of the masterpiece it can be. There are two main issues with the current version of this problem (think about it for a while and you’ll see what I mean):

  1. It’s easy for students to eyeball an optimal solution. So they come back to my office and say: “I don’t know what the point of this problem is; the answer is obviously equal to …” Many of them don’t even try to create a math model.
  2. Even if you model it incorrectly, that is, by choosing the wrong variables which will end up double-counting the number of people covered by the ambulances, the solution that you get is still equal to the correct solution. So when I take points off for the incorrect model, the students come back and say “But I got the right answer!”

After a few years of facing these issues, I decided I had had enough. So I changed the problem data to achieve the following (“evil”) goals:

  1. It’s not as easy to eyeball an optimal solution as it was before.
  2. If you write a model assuming every region has to be covered (which is not a requirement to begin with), you’ll get an infeasible model. In the original case, this doesn’t happen. I didn’t like that because this isn’t an explicit assumption and many students would add it in.
  3. If you pick the wrong set of variables and double-count the number of people covered, you’ll end up with an incorrect (sub-optimal) solution.

These improvements are obtained by adding a sixth region, changing the table of distances, and changing the population numbers as follows:

The new population numbers (in 1000’s) for regions 1 through 6 are, respectively, 21, 35, 15, 60, 20, and 37.

I am now much happier with this problem and my students are getting a lot more out of it (I think). At least I can tell you one thing: they’re spending a lot more time thinking about it and asking me intelligent questions. Isn’t that the whole purpose of homework? Maybe they hate me a bit more now, but I don’t mind practicing some tough love.

Feel free to use my modification if you wish. I’d love to see it included in the 7th edition of Cliff’s book.

Note to instructors: if you want to have the solution to the new version of the problem, including the Excel model, just drop me a line: tallys at miami dot edu.

Note to students: to preserve the usefulness of this problem, I cannot provide you with the solution, but if you become an MBA student at the University of Miami, I’ll give you some hints.

7 Comments

Filed under Books, Integer Programming, Modeling, Teaching

MLB Umpire Scheduling

There are two purposes to this post. First, I’d like to follow-up on Michael Trick’s post on the importance of teaching and its relationship with research. One of the points Mike makes is that your next exciting research or consulting project may come from current or former students. Those of us who teach undergraduate and MBA classes have the opportunity to network with (future) managers and practitioners who will eventually put their training to the test, producing actual answers to real-life problems. And if one of those problems requires more OR knowledge than what they had the opportunity to learn in school, they might remember their friendly neighborhood OR professor. Another way research can come out of teaching is during hands-on projects. Back in 2006, Mike was in charge of an elective OR-project class that allows MBA students to try their hands on a real-life problem; in that case umpire scheduling. To my delight, Mike invited me to be the TA for that course and I gladly accepted. The rest is history.

The second purpose of this post is to help myself keep track of the recent news stories about our umpire scheduling paper. Thanks to an excellent job by the PR departments at the University of Miami School of Business (thanks, Catharine!) and Michigan State University, the story has appeared in numerous outlets. As a matter of fact, I’m very excited to report that Scientific American had a 60-second science podcast about our work:

August 18Scientific American: Researchers Tell Umpires Where to Go (PDF version)

Here are a few other news outlets that covered the story (I’m trying to keep this list up-to-date for my own sake). I’m also providing a link to a PDF version of each story in case the web pages are taken offline:

April 2012, The Spring issue of Business Miami Magazine has an article about our work entitled Road Trip (PDF version).

October 19, WAMC Northeast Public Radio Academic Minute. I recorded a 1:45-minute explanation of the problem, approach, and results which aired as one of WAMC’s Academic Minutes on the same day of the first game of the World Series. That was a lot of fun! Click on the link to listen. If the link doesn’t work, here’s the MP3 file.

September 6, Miami New Times: Tallys Yunes, UM Professor, Solves MLB’s Umpire Scheduling Dilemma (PDF version). This article also appeared in print, in the September 8-14 issue of Miami New Times. Here’s a PDF scan of that.

August 3, PhysOrg: University of Miami Business Professor Helps Create a Successful Scheduling Method for Umpires in Major League Baseball (PDF version)

August 3, HPCwire: Business Prof Solves Traveling Umpire Problem for Major League Baseball (PDF version)

July 31, University of Miami School of Business: School’s Management Science Research Resolves Major League Baseball’s Umpire Scheduling Challenges (PDF version)

July 21, ScienceDaily: Scholar Helps Make Major League Baseball Umpire Schedule a Hit (PDF version)

July 21, ThePostGame: MLB Umpires Have a Turkish Secret Weapon (PDF version)

July 20, PhysOrg: Michigan State Scholar Helps Make MLB Umpire Schedule a Hit (PDF version)

July 20, Michigan State University News: Michigan State Scholar Helps Make MLB Umpire Schedule a Hit (PDF version)

I greatly enjoy the teaching side of my job because I believe it complements the research side quite well. I’m looking forward to bringing articles like the ones above to my classes in the Spring and I’m sure they’ll be well received.

Further acknowledgments: thanks to those who also helped spread the word about the umpire scheduling problem on Twitter, especially Paul Rubin (@parubin), Aurélie Thiele (@aureliethiele), and @INFORMS (is that you, Mary Leszczynski? :-).

3 Comments

Filed under Applications, Heuristics, Promoting OR, Research, Sports, Teaching, Traveling Umpire Problem

Big Bang Theory Party Planning

Penny is organizing a party at her apartment, but she is on a tight budget. Having a working knowledge of all of the important things in the universe, Sheldon knows everything about linear programming and offered to help her. He postulates that it’s ideal to have two kinds of mixed nuts: a plain party mix, and a luxury mix (for those with a distinct taste like himself). Based on the expected number of guests, Howard quickly calculates that they’ll need a total of at least 10 pounds of snacks, but no more than 6 pounds of each kind of mix. On his white board, Sheldon has already come up with the following table:

Raj wants to dip the hazelnuts into liquor, but that’s not in the budget, so he gives up. Leonard reminds everyone that, because of their allergies, it’s important to keep the average allergenicity level per pound in both mixes to no more than 3. Write an optimization model to help Penny prepare the two kinds of snacks at minimum cost. But be careful: Sheldon will check it later for correctness!

This post is part of my series “Having Fun with Exam Questions”. Previous questions dealt with Farmville, vampires, and (potentially) Valentine’s day.

1 Comment

Filed under Big Bang Theory, Exam Fun, Linear Programming, Modeling, Teaching