WIXLIB

Business Analytics: The Past,Present and Future ofOperations ResearchEWO 2013Michael TrickTepper School of Business, Carnegie MellonUniversity1

THE PAST2

Example 1: A New Model for PackageDelivery 1973: Fred Smith, avidpilot, had an ideaProvide “taxi service” forpackagesFred knew the south-eastso began there11 cities were linked inthe now-famous model:fly everything toMemphis, re-sort, and flyeverything back3

Result Enormous failure 6 packages on day 1 (including one from Fred)Not much better on days 2 and 3Closed on day 4What to do?4

Example 2: Yahoo! versus Google2002. Yahoo! has weathered the crash of the internetbubble. Sees (correctly) that search-basedadvertising is a big thing (it is currently a US 15billion/year business segment)Proposes US 3billion to buy Google (then with yearlyrevenues of US 240 million) but is rebuffedPurchases Inktomi and Overture to compete withGoogle5

Search Market Advertising Share 2002: Overture revenues twice Google2003: Overture equal to Google2005: Google 2.5 times Yahoo/Overture2007: Google over 70% of entire marketWhat Happened?6

Example 3: The UnitedStates Postal Service Yearly delivers more than 200 billion piecesof mail to 144 million locations in the USRevenue: about US 70 billion, notincreasingQuasi-governmental agency, required to existwithout government subsidies7

Mail Processing FacilitiesAbout650 mailprocessingfacilities!8

Reorganization All previous attempts to rationalize thestructure of USPS were met withcongressional intervention and controversyNo doubt saving possible, but how?US 70 billion/year company becomes a“poster child” for inefficiency and bureaucracyWhat to do?9

Key IdeaOperations ResearchBusiness Analytics!10

Operations Research11

Business Analytics is a Hot Topic“Business analytics”12

. MaybeManagementscienceOperations researchBusinessanalytics13

Strawman: The OR ProcessIdentify aProblemImplementSolutionFormulate a ModelDetermineDecisionsObjectivesConstraintsGet DataEstimate Missing DataValidate SolutionIs it reasonable?SensitivityFind Solution to Modelusing Mathematical Tools14

The Business Analytics ProcessIdentify aProblemImplementSolutionFormulate a te SolutionIs it reasonable?SensitivityEmbed data process inmodelGet DataEstimate Missing DataFind Solution to Modelusing Mathematical ToolsGet DataEstimate Missing Data15

Operations Research/BusinessAnalyticsUsing past data to predict thefuture and make better decisionsbased on that prediction It is really what the best operations researchhas always beenRecognition that OR “tool kit” needs to movebeyond optimization to include predictiveanalytics (like data mining)16

BUSINESS ANALYTICS: THEPAST OF OPERATIONSRESEARCH17

Back to our stories: Fred Smith Fortunately, Fred is smart enough to knowwhat he didn’t knowHad a physicist friend analyze the situation Key is route structure Some cities that generate lots of small packagesSome cities that require lots of small packages18

First model Estimate demand for 112 cities (112 by 112 about12,000 data pointsDetermine competition on routes to get FedEx’sshare Found some great possibilities: Rochester had tons ofsmall packages (think Kodak) with poor air serviceNew Orleans was poor choice (Delta provided more thanenough service) Solve problem: what is the most profitable set ofcities to include in the network? Business Analytics: key is data here!19

Result 23 city network that was much different thaninitial oneBusiness grew quickly and continues to thisdayAlmost no strategic decision is made withoutOR analysisFedEx is an Operations Research companythat delivers packages20

Example 2: Yahoo! versus Google Yahoo! was built on a hand-edited collectionof carefully classified links. Pretty reasonablewhen there were only 30-40 new sites in adayMy own site was about the 800th site in theworld, and joined yahoo as about the fourthoperations research site21

Google Google was built on the automaticidentification of the “best page” for anysearch.The question of the “best page” for a searchis an operations research question.The cleverness of Brin and Page in “solving”this was really in formulating it: thetechniques used are (or were: lots has beendone since) standard.22

Google’s page rankDetails unimportant: based on ideaof assigning importance to each webpage in a consistent way (where importanceflows through links on a page)Easily understood by OR undergrads (you,if you understand eigenvectors!)23

Business Analytics Real key is to recognize the network of linksas data Constantly updated as network updates Alternative of a static analysis unappealing inthis environment24

Why did Yahoo! “fail”?From a Wired article on Terry Semel (CEO 2001-2007) ManyLackofhaveunderstandingofYahootechnicalwhomet with him atsay heaspectsstill doesn'tknowthe right questions to ask about technology. "Terry(arguably)could never pound the table and say, 'This is where weneed to go, guys,'" one former Yahoo executive says. "Onthose subjects, he always had to have someone next tohim explaining why it was important." One could havemade a convincing argument two years ago that such deeptechnical knowledge didn't matter much. But now we haveempirical evidence: At Yahoo, the marketers rule, and atGoogle the engineers rule. And for that, Yahoo is finallypaying the price.25

US Postal Service To break the political logjam, create anindependent, politics-free model anddetermine an “optimal solution”Test the solution against the real-world.Use the model to determine cost of politicalinterference26

Result Results suggest that the correct size of thenetwork is approximately 350 facilitiesNetwork “looks different”: many morefacilities specializing in types of mail, ratherthan handling all mail from a regionInitial proposal to close more than 130facilities. Expected savings: more thanUS 2 billion/year with improved service27

US Postal Service: ResultsSample Conversation:Congressman: why are you closing Wheeling, WV and movingthe work to Pittsburgh? Why don’t you close Pittsburgh andmove it to Wheeling?Reponse: That change would cost an additional 12 million incapital costs and 7.8 million in yearly costs. If you can convinceyour colleagues (including the Pittsburgh congressman) that it isworth it, we’d be happy to make the change.Congressman: Oh.28

Too slow to implement?Washington Post, March 29, 201329

Business Analytics? Given the data environment, difficult to domuch prediction Where is mail volume going?30

Mail volume projections31

BUSINESS ANALYTICS: THEPRESENT OF OPERATIONSRESEARCH32

Why now? Trends are moving towards more OR Increased DataFaster ComputersBetter AlgorithmsLower Fixed Cost for OR33

Increased Data34

Big Spending Yearly global spending on informationtechnology: 3.5 trillion.35

OR Role Data is not information; information is notimproved decision making Operations research/business analyticsallows companies to make better decisionsbased on the data they are collecting36

Faster Computers: Supercomputer and otherwiseIntel i7 (6 core) 569 fromBest Buywww.top500.org37

Faster computers increases the relevanceand applicability of OR Example. Sports scheduling example Time (1996): 18 days to solve (impractical)Time (2007): 30 minutes to solve (practical)38

Algorithms Key to OR is algorithms to find “bestdecisions” relative to a mathematical modelAlgorithms often very sophisticated: goal isto quickly find the best decision among ahuge (e.g. more than the number of atoms inthe universe) number of choicesExtremely active area for both academia andbusiness: there are many firms whosebusiness model revolves around a newalgorithm39

Algorithms are getting better also!My sports scheduling examplenow solves in about 3 seconds!Bixby,APMOD201240

Speed The combination of improved algorithms andfaster computers mean that many problemscan now be solved 1 billion times faster thanthey could 10 years ago. Huge increase in applicability of OR methods41

Illustration: TSP with 2392 nodes1987: Padberg and Rinaldi2011: Bill Cook and Concordewith iPhone42

Lower Fixed Cost for OR Past. Big projects for big companies Fighting World War IIAirline Crew SchedulingMaterial Planning at FordCurrent. Much more accessibleOR on your computer (Solver in Excel)43

44

BUSINESS ANALYTICS: THEFUTURE OF OPERATIONSRESEARCH45

Future is bright!IBM 2010 Annual report; contrast “cloud” at 7 b and smarter planet 10 b46

Themes for the Future Closer link between predictive analytics andprescriptive analyticsHandling uncertainty to create robustsolutionsExploiting parallelism, or lose Moore’s LawNew areas of applicationOptimization with adversaries47

Example Large automobile parts supplierReceives estimates of order quantities sixmonths in advance (which are then regularlyupdated)Uses estimates to do capacity planning, shiftscheduling, etc.48

Capacity Planning Well solved, classical operations researchproblem Issues of level of detail, scheduling, etc. etc. But what about data ?49

Problem Estimates were (sometimes) terrible:January: “I’ll need 1000 in June”February: “I’ll need 2500 in June”March: “I won’t need any in June”April: “I’ll need 10,000 in June”May: “I’ll need 500 in June”June: “Where are the 5,000 I need?”50

Business Analytics Approach toCapacity planning Capacity planning needs to adapt to themessy data environment.One step: clustercustomers basedon accuracy of theirforecasts51

Other Examples Revenue management and prediction of “noshows”Text mining to estimate stock variability andoptimal portfolios52

Handling Uncertainty and Robustness Many approaches for handling uncertainty inmodels Replacing with mean, or some %tile (USPScapacity planning)Scenario optimizationStochastic programming“Robust” optimization (assumptions on ranges,number of changes of data)53

True measures of robustness? What does a robust solution really mean?David Ryan and others on robust airline crewschedulesBoth planesnow lateAirport54

Measure of Robustness Unclear where uncertainty is. Model storms?Politics? Baggage handling?Use “plane changes” as surrogate.Schedules with few plane changes arenaturally more robust.Get robustness at little cost6000Non-robustness 500040003000200010000880930980Cost103055

Data-free Robustness Bartholdi and Eisenstein: scheduling shuttlebuses. Don’t! At checkpoint, use rule “Wait60% of the time until the bus behind willarrive at the checkpoint”Robust to changes in traffic congestion,passenger load times, and even number ofbuses!56

Other applications? Badly need some measure of robustness forfinancial markets: historical variance doesn’tseem to work well.Scheduling: include simple robustness inMajor League Baseball scheduling57

Parallelism Back to the “top 500”:58

Risk for some types of operationsresearch Some of what we do seems hard toparallelize: Simplex-based linear programmingMany network algorithmsDynamic Programming59

Effect on Mixed Integer Programming Hans Mittelmann’s benchmarks:Not a lot of halvingof time between the6 and the 12 columns!60

Challenges In order to keep up with computer speedimprovements, we need to improve parallelperformanceAlternative algorithms? Perhaps formerly“failed” algorithms now seem moreappealing?61

New Areas of Application Traditional view of OR: ManufacturingServices limited to transportation and logisticsNew view OR everywhereServices are a great opportunity62

63

Example application64

65

Lots of other areas of application Medical procedures Kidney transplant chainsEducationUrban developmentCall center optimizationCustomer optimization66

Adversaries As OR combines with predictive analytics,more likely to face adversaries workingagainst model assumptions Best Buy searching for “bad customers”Google in never-ending fight against spammersand those who game rankingsBut we are pretty good at that.67

Which completes theloop to OR Past68