Tag Archives: public policy

operations research improves school choice in Boston

Many cities allow families to choose elementary schools to address growing inequities in school instruction and performance. School choice lets families give a rank ordering of their preferred schools, and a lottery ultimately assigns students to schools. The result is that many students have to travel a long way to school, crazy bus schedules, and students on the same block who do not know each other because they go to different schools.

Peng Shi at MIT (with advisor Itai Ashlagi) won the 2013 Doing Good with Good OR Award held by INFORMS with his project entitled “Guiding school choice reform through novel applications of operations research” that addressed and improved Boston’s school choice model.  I am pleased to find that his paper based on this project is in press at Interfaces (see below).

The schools in Boston were divided into three zones, and every family could choose among the schools in their zone. Each zone was huge, so on any given block, students might be attending a dozen different schools. See a graphic in a Boston Globe report to see more about the problem.

Peng balanced equity with social problems introduced with the choice model by proposing a limited choice model. His plan was to let every family to choose among just a few schools: the best and the closest. Families could choose from the 2 closest in the top 25% of schools, the 4 closest in the top 50% of schools, and the 6 closest top 75% schools, the 3 closest “capacity schools,” and any school within a mile. There was generally a lot of overlap between these sets, so families had about 8 choices in total (a lot less than the original school choice model!). This gave all families good choices while managing some of the unintended consequences of a school choice system (busing and transportation, distant schools, neighbors who didn’t know each other).

The model itself was not obvious: there is no “textbook” way to model choice. Peng visited with the school board and iteratively adapted and changed his model to address concerns within the community.  This resulted in the model becoming simpler and more transparent to parents (most parents don’t know about linear programming!). The new model pairs above average schools with below average schools in a capacity-weighted way to make school pairs have comparable average qualities. This lets families choose from school partners, the closest four schools, and schools within a mile.

The school board voted to adopt his plan. Peng worked with the school district to come up with important outcomes to evaluate. The model itself uses linear programming to “ration” school seats probabilistically among students by minimizing the expected distance subject to constraints. To parameterize the model, he used a multinomial logit model to fit the data (with validation). He also ran a simulation with Gale-Shapley’s deferred acceptance algorithm as a proof of concept to ensure that the model would work.

See Peng Shi’s web site for more information. Some of his documentation is here.

I’ve been on the INFORMS Doing Good with Good OR Award committee for the past three years. This award honors and celebrates student research with societal impact. I love this committee – I get to learn about how students are making the world a better place through optimization. And these projects really do make a difference: all applications must submit a letter from the sponsor attesting to improvements. Submissions are due near the end of the semester (hint hint!)

Reference:

Guiding School-Choice Reform through Novel Applications of Operations Research by Peng Shi
Interfaces articles in advance
Permalink: http://dx.doi.org/10.1287/inte.2014.0781


operations research for drug policy and addiction

I enjoyed listening to Jon Caulkins’ Omega Rho lecture at the INFORMS Annual Meeting. The abstract for the talk is:

Operations Research in Service of Drug and Addictions Policy: Lessons from and for the Discipline of Operations Research
Jonathan P.Caulkins
H.Guyford Stever Professorship of Operations Research and Public Policy
Carnegie Mellon University

I am an OR missionary. I have carried our tools and perspectives into the fields of drug policy and addiction. When traveling far afield, one often encounters opportunities to do good by applying what seem to be quite basic precepts back home, and one returns with a deeper understanding of one’s own culture and its strengths and weaknesses. That has certainly been true of my professional tour. I will share success stories – instances in which by virtue of being the only person thinking about an issue from the perspective of a math modeler, I was able to make fundamental contributions by doing analyses that anyone with training in OR would view as quite elementary. I will also try to share some insights into our disciplinary culture. Drug policy, like most policy domains, is inherently interdisciplinary. So I work with scholars from many disciplines. That experience has given me an appreciation of different disciplines’ strengths and limitations when grappling with messy unstructured problems. I firmly believe that diversity is essential to good decision making, including disciplinary diversity. But I am also interested in which disciplines’ graduates are leaders, not just members, of the teams that shape high-level and strategic decision making. I will close with some thoughts about how we might increase our discipline’s “market share” within t! hose leadership roles.

This was an interesting talk about being an OR practitioner and solving real problems. Jon talked about the general principles he uses to influence policies. This involves doing good work, but more importantly, it involves asking good research questions. Jon asks excellent research questions. Jon summarized the impact his answers to these questions have had on policy. Jon’s work modeled drug lifetimes and life cycles using Markov chain models, a feature common to all drug types that could be used to forecast when drugs would go out of favor. He talked about modeling types of users–heavy and light–and the insights one can obtain when considering different classes of users. I enjoyed the discussion on pricing and drug purity, two issues that are often overlooked by decision makers and therefore have impact.

A really great part of the talk was when Jon took on Big Data. He said that in his experience, being the first with any data at all is really important for influencing policy. Many times, public safety leaders make decisions with zero data points or one data point (an anecdote!). Going from 0 to 100 data points can change a policy, going from 100 data points to “Big Data,” not so much.

David Hutton blogged about Jon’s talk on the INFORMS2014 blog [Link].

Earlier posts about Jon Caulkins’ talks:


reverse auctions for the television spectrum and graph coloring problems

Karla Hoffman from George Mason gave an nice talk at the 2013 INFORMS Computing Society Conference about reverse auctions to buy back the TV spectrum. It is an issue if you still use an antenna to watch TV (see the bottom of this post if you are shocked that people still use antennas).

Here is the problem. Once upon a time, the FCC gave the networks the bandwidth. Changes in technology — the move to digital and the needs of broadband — have motivated the need to reassign the spectrum to stations. This will happen in 2014.

The reverse auction problem of assigning networks to a piece of the spectrum. A station requires 6MHz of the spectrum plus a buffer. The same piece of the spectrum could be assigned to stations in, say, Denver and Baltimore. The same antenna would not be able to pick up both stations, and therefore, there would be no interference.  But different stations in, say, Washington DC and Baltimore could not share the same piece of the spectrum.

This leads to a graph covering problem:

  • the TV stations are the vertices
  • there is an edge between two TV stations if the TV stations are nearby (i.e., an antenna could pick up both stations if they are close enough)
  • 6MHz chunks of the spectrum are the colors.

If you’re not familiar with the graph (or vertex) coloring problem, here is the general idea. It is an assignment of “colors” to vertices on a graph, where no two adjacent vertices share the same color [Link]. Coloring a map is a type of graph coloring problem on a planar graph, where the states are the vertices and there is an “edge” between two states if they share a border. This leads a map where no two adjacent states have the same color (see below).

Example of a solution to a graph coloring problem

There are some additional side constraints in the TV spectrum coloring problem, such as UHF and VHF designations and public service space reserved in the spectrum. It’s a complex problem.

The graph coloring problem is a feasibility problem (can I color my graph with 4 colors?) There are only so many “colors” available in the TV spectrum. The graph coloring problem described above could thus lead to infeasible solutions, and this may be an issue in the auctions (a bid should not be accepted if that would lead to an infeasible solution). This motivates the need for a feasibility checking routine during the auctions. Later, broadcasters that do not participat or whose bids are not accepted must be reassigned to the remaining TV stations available.

In terms of the auctions, there are plenty of other challenges, such as planning what the auction will look like, how pricing will be handled, and how one will determine a winner.

In the US, about 10% of people use antennas. Two people in the audience (including me) still use bunny ears. This was such  shocking news for one attendee that he posted it to twitter:

Mike Trick

I try to stay too busy blogging to have time for TV (:

I probably got some of the details about the auctions wrong. It’s a complex problem and Karla did a great job of distilling the essence of the problem without overwhelming us with unneccessary details (there were a lot of necessary details). If you know more about these auctions and how OR will be used, please leave a comment.

Related posts:


the exit polling supply chain

A WSJ Washington Wire blog post describes the Presidential election exit polling supply chain in New York in the immediate aftermath of Hurricane Sandy. The Washington Wire blog post highlights the polling firm Edison Research, based in New Jersey. Edison provided the questionnaires used by pollsters who would collect information about the ballots cast. As you might recall, New Jersey and New York were extremely damaged from the hurricane.

Questionnaires

One of the logistical challenges was in printing and delivering the questionnaires used by pollsters around the country. The questionnaires need to be timely, so they are usually shipped one week before the election. Sandy was on track to strike 8 days before the election, so a rush order was placed with the printer. Two thirds of the questionnaires were mailed before Sandy struck and Edison’s election office lost power along with the rest of New Jersey. The rest of the questionnaires were stored for two days until they had to be shipped. Edison printed the mailing labels from their main office, and then UPS shipped the 400 packages to pollsters via Newark Airport. While Edison had redundancy in their system (e.g., the mailing labels could be printed in another facility and a redundant system alerted employees of the change), it only worked because not all of their offices lost power.

Mail Delivery

While Edison relied on UPS to deliver the mail, it is worth noting that USPS mail service continued as normal except for one day during Hurricane Sandy (HT to @EllieAsksWhy).

Gas

Edison relied on having employees implement Plan B. With the gas shortage, it was difficult for employees to get to work when they needed to save gas for other car trips. Organizing car pools was more difficult than normal, since employees could not rely on communicating by email or cell phone.

Hotels

As I mentioned in an earlier post, there were few/no vacancies at hotels that had power, which provided challenges for Edison employees who wanted to work out of a hotel (most offices and homes were without power) or pollsters who needed to travel to different cities to perform exit polling.  I’m not sure how these issues were resolved.

Local transportation to the polls

The NYC public transportation was up and running on election day, so the pollsters could make it there for the big day. The subway reopened with limited runs the Thursday before Election Day and was running as usual on Election Day.

What if Hurricane Sandy came later?

Edison Research managed, but having an 8 day head start was helpful for successfully completing a contingency plan. If the hurricane hit 5 days or closer, the questionnaires would have already been printed and mailed. However, there may have been more challenges with getting pollsters to the polling locations in New York City and other locations (the subway may still have been closed on Election Day).

Related posts:


a gun offender registry: everyone wants one but the costs and benefits are a mystery

Prince George County in the Washington DC is weighing a bill requiring a gun offender registry, and a vote is expected in early June. If it passes (and it is expected to do so), the county would allow/require police to monitor gun offenders. I think this is akin to the sex offender registries but for those convicted for gun-related violence.  Prince George County is not the first to pursue a gun registry. Gun registries are a trend in local governments across the nation.

Supposedly, gun-offender registry have had “an impact.” I am not surprised. But they surely come with a cost. The cost in this case is a decreased manpower of already-understaffed police force. No one wants to appear soft on crime, but no one wants to pay for it either. I was surprised that the NRA representative quoted in the article appeared to be the most sensible in his assessment of the tradeoffs:

Andrew Arulanandam, the National Rifle Association’s director of public affairs, said his group advocates vigorous enforcement of existing gun laws rather than the creation of new databases. Running a gun-offender registry, he said, requires taxpayers to foot the bill for computer equipment and IT professionals, and it could take officers off the streets and place them in administrative jobs.

Gun registries could be effective despite the costs. If those on the gun registries are “dangerous,” then monitoring those individuals more closely could be an effective use of police manpower, since it focuses police attention on those most likely to commit dangerous crimes. That could more than make up for the policing that is foregone due to the new responsibilities associated with the registry. But I need to see some research that honestly shows the level of impact that registries could have. The police chief in Prince George does indeed intend to use some of their existing 1400 police officers to monitor the gun registry.

[Deputy Police Chief Craig] Howard said police would initially assign a sergeant and four or five detectives to handle the gun registry, pulling them from other jobs in the department. He said the creation of the computer database could be handled by those who run the department’s sex-offender registry and do other IT work.

The 5-6 officers needed for the registry are less than 1% of the police force. But the current registry level is zero and the system is not in steady-state. The registry will likely grow in time as gun offenders are added, necessitating an increasing number of police officers to monitor the registry. I’m not sure that monitoring the registry in the future will be sustainable.

I am agnostic on gun registries. I am not agnostic about honesty regarding the true cost of gun registries and their impacts. Certainly, different municipalities and counties need to weigh the costs with the rewards and make a decision that they can live with. Previous attempts to curb crime—such as the Three Strikes Laws and minimum sentencing—have lowered crime at an enormous cost. The costs here are associated with an exploding prison population. I suspect that the same might be true for gun registries.


elections and OR

With election day coming up on Tuesday, the latest Punk Rock OR Podcast episode addresses elections and OR. You can listen here:

Here are a few show notes and links to extra material.

Walter Mebane, Professor of political science and statistics at the University of Michigan, has written several articles about under-staffing voting locations, election fraud, and election forensics (he may be a political scientist, but his papers have figures that look like they are made in R. Not too shabby). Check it out.

You are more likely to die in a car accident on Presidential election days. Here is the JAMA article that summarizes this disturbing research finding (and a Scientific American podcast about it).

University of Cincinnati PhD student Muer Yang developed a simulation model to reduce and equalize voter waiting times across different voting areas. This is a good example of using OR for elections.

How did the University of Illinois student body elect a gnome and snail for the student body president and vice-president, respectively? Technically, they didn’t. The gnome and snail were disqualified after winning a plurality of the vote, and the controversy led to an investigation. Here is the full story according to the snail. Amazingly, all of this is real.

We followed up on our last episode on pirates and OR. We found a new article in the Journal of Transportation Security that presents statistics on pirate attack success rates.

Don’t forget to email me with your OR jokes. And don’t forget to vote!

Vote!


community based operations research

Michael Johnson, PhDI had the pleasure of interviewing Michael Johnson about his upcoming book Community Based Operations Research in a Punk Rock OR Podcast (21 minutes). It’s a fantastic book: I recommend that you ask your university library to add it to their collection.  If you are heading to the INFORMS Annual Meeting and are interested in CBOR, you might want to check out the two panels that Michael Johnson is chairing.

If you cannot wait for your copy of CBOR to arrive in the mail, I recommend reading Michael Johnson and Karen Smilowitz’s INFORMS Tutorial on CBOR. It’s a must read!

Other Podcasts can be found here.


Follow

Get every new post delivered to your Inbox.

Join 2,767 other followers