Success Stories of Linear Programming

Goals of this lecture z Introduce an interesting application area for linear programming called Data Envelopment Analsysi (DEA) z Turn it over to Ph.D. student Lincoln Chandler, who will talk about his research using DEA Introduction to Data Envelopment Analysis z The goal of DEA is to measure whether individual units (or firms) are “efficient” z It contrasts efficiency in terms of seeing if they produce outputs effectively given their inputs. z Developed by Charnes and Cooper in 1970’s Measuring efficiency is difficult z Suppose that one is measuring efficiency in a hospital. – Which is of more value: treating middle aged patients or older patients? – Which takes more resources? z If we treat all patients as equal, then hospitals may have an incentive to treat healthier and younger patients because they make a hospital look efficient. – DEA avoids this issue by looking at each hospital in the best possible light. Hospital Data Inputs Outputs Hospitals 1 2 1 2 3 H1 5 14 9 4 16 H2 8 15 5 7 10 H3 7 12 4 9 13 INPUTS: 1. Hospital Beds 2. labor (1000s of hours) Outputs: measured in 100s of patient days for patients 1. under age 14 2. ages 15 to 65 3. older than age 65 Measuring Efficiency z Assume that input i has a cost wi. z Assume that output j has a value tj. Value of outputs Efficiency = Cost of inputs We will determine the w’s and t’s later. More on efficiency Inputs Outputs Hospitals 1 2 1 2 3 H1 5 14 9 4 16 H2 8 15 5 7 10 H3 7 12 4 9 13 E (H1) = 9Value t1 + 4of t2 outputs + 16 t3 Cost inputs 5 w1 of + 14 w2 Is Hospital 2 efficient? This is interpreted as: Can we assign positive costs to the inputs and positive values to the outputs in such a way that Hospital 2 is at least as efficient as the other hospitals. That is, can we assign costs and values so that E(H2) ≥ E(H1) and E(H2) ≥ E(H3)? These will be non-linear constraints, but we can fix that. E (H2) = 5 t1 + 7 t2 + 10 t3 8 w1 + 15 w2 ≥ E (H1) = 9Value t1 + 4of t2 outputs + 16 t3 Cost inputs 5 w1 of + 14 w2 Making the problem for H2 an LP Step 1. (conceptual step). Multiply costs of inputs by a constant so that the cost of the inputs for H2 is exactly 1. That is, choose w1 and w2 so that • 8 w1 + 15 w2 = 1 Step 2. (conceptual step) Multiply through the values of the outputs by a constant so that E(H1) ≤ 1 and E(H3) ≤ 1. Maximize the value of the outputs of H2 subject to the cost of the inputs for H2 is 1 E(H1) ≤ 1 and E(H3) ≤ 1. costs and values are strictly positive Making the problem for H2 an LP Maximize the5value t1 + 7of t2 + the 10outputs t3 of H2 subject to the 8cost w1 +of15 the w2inputs = 1 for H2 = 1 E(H1) ≤ 1 9 t1 + 4 t2 + 16 t3 ≤ 5 w1 + 14 w2 E(H3) ≤ 1. 4 t1 + 9 t2 + 13 t3 ≤ 7 w1 + 12 w2 costs and values positive t1, t2, tare 3, wstrictly 1, w2 ≥ .00001 9 t1 + 4 t2 + 16 t3 5 w1 + 14 w2 ≤1 4 t1 + 9 t2 + 13 t3 7 w1 + 12 w2 ≤1 On H2’s efficiency z The optimal efficiency for H2 is .773 – H2 is inefficient. z The optimal efficiency for H1 and H3 is 1. – H1 is efficient and H3 is efficient – found by solving two more linear programs) On the intuition for H2’s inefficiency. Inputs Outputs Hospitals 1 2 1 2 3 H1 5 14 9 4 16 H2 8 15 5 7 10 H3 7 12 4 9 13 Consider a Hospital H4 by taking .3381 * H1 + .8555* H2 H4 6.759 15 6.465 9.052 15.532 H2 uses more inputs than H4, and produces at most .773 of any input. Summary z Data Envelopment Analysis is a “hospital friendly” way of measuring efficiency of hospitals. – the hospital units can use any costs for inputs and any values for outputs – Is there some way of choosing costs and values so that the hospital is more efficient that every other hospital? DEA in Practice: Accomplishment, Caveats, and Applications DEA in Practice: Bank Branches* z The banking industry, like others, has experienced a great deal of consolidation over the last twenty years Bank Boston Fleet Bank of America DEA in Practice: Bank Branches z Pre-Merger Expectations – Increased profits from economies of scale – Broader service offerings / customer base – More competitive z Post- merger realities – “Merged entities” still operate as if independent – Minimal increase in cost efficiency – 2 out of 3 bank mergers generate “disappointing” returns to shareholders DEA in Practice: Bank Branches z Despite the benefits of merging front-end operations, companies often postpone or forego this opportunity – Politics – Short-term economic targets – “Don’t fix what isn’t broken” z A DEA study was used to gauge the savings loss from not merging operations Outline of the Study z DEA was used to compare the branch efficiency of four banks that had been merged into one (over 200 branches) z Branches were compared within each parent bank, and then across the merged bank to determine efficiency loss, which relates to potential savings z After four years, the merged bank had realized cost savings of about 8%; a comparison of savings estimates would help estimate the value of merging branch operations, a unrealized opportunity The Bank Branch as a DEA Unit z 2 inputs, 6 outputs Results z The analysis indicated substantial opportunities to achieve additional savings – When measured within the parent group, the average efficiency gap was about 7% – When measured across the system, the average efficiency gap was 23%, over three times higher! z DEA was able to quantify a major source of unrealized shareholder value More on DEA z Given a set of business units, DEA provides a method of measuring relative efficiency, even for systems with multiple inputs and outputs. z For each inefficient unit, DEA also provides a reference set of efficient units for guiding improvement strategy. z The flexibility of DEA has led to its application in a wide variety of studies, including: – Capacity Management of Fishing Fleets (Denmark) – Hotel Room Utilization (United Kingdom) – Hospital Performance (Oman) – Brand Management of Business Schools (United States) DEA in Public Schools z My current research involves the use of DEA to measure relative efficiency in a public school district. z My emphasis is on elementary schools located in large U.S. cities z My work is towards a refined DEA model that: – Recognizes the influence of leadership on school outcomes – Clarifies the relation between school effectiveness and efficiency – Facilitates improved strategies for management Background z There is some literature on DEA and school efficiency – Bessent and Bessent, 1980 – Examined educational efficiency at the district, school, and individual level z Few impacts of DEA studies on educational practice – DEA as a measurement, or sorting, tool… – Studies have not identified “best practice.” – DEA studies have not lead to improvements in system productivity Recent Comments on Public Schools z "America's high schools are obsolete" and are "ruining the lives of millions of Americans every year." – Bill Gates, Feb. 26, 2005* z “Low-income families are also losing faith in these [public school] districts… they have to figure out how they create systems to take school reform to scale.” – Warren Simmons, Exec. Director, Annenberg Institute for School Reform** Creating an DEA Model for Education z My research – create a DEA model that compares the efficiency of elementary schools in the Chicago Public School system z Next major step: – identify a good set of inputs and outputs for the analysis – Inputs: school resources – outputs: school outcomes Creating the Model z Determining which inputs to add into the analysis can be a complicated, and iterative, task z Things to consider while creating the model – “Granularity” of Inputs/Outputs – Quality and Availability of Data – Fidelity of the Model z Class exercise: brainstorm on plausible inputs and outputs Summary of Main Research Ideas z Schools are usually compared using 1-2 output measures z DEA provides a richer method of comparison by considering inputs as well z DEA can provide additional insights into reform strategy – We can identify specific peer schools to look for best practices – We can reveal inefficiencies in otherwise high performing schools References on DEA z Books (Available in Dewey) – Charnes et al., “Data Envelopment Analysis: Theory, Methodology, and Application”,1994. – Ray, S. “Data Envelopment Analysis”, 2004.