My interest in public sector operations research has led me to appreciate so-called “wicked problems” (as opposed to “tame” problems). Wicked problems often reflect the soft side of operations research and are why some models are so complex. Due to the social component of the problem, there are many stakeholders with contradictory needs. A problem that is wicked quickly unravels due to the connections it has to other issues that are also social, and so on. Russell Ackoff summed this up nicely:

“Every problem interacts with other problems and is therefore part of a set of interrelated problems, a system of problems…. I choose to call such a system a mess.”

Here are a few slides on wicked problems from my Public Sector OR course:

I recommend C. West Churchman’s guest editorial in Management Science in 1967, where the term “wicked problems” was coined [pdf: Wicked Problems Churchman 1967] and this nice article on “wicked” problems by John Mingers in OR/MS Today.

Related reading:

• Planning problems are wicked problems
• In defense of model complexity
• optimization and unhappy truckers
• operations research is optimistic
• Read my public sector OR course blog

I am teaching a course on Public Sector Operations Research this semester. I included this quote from a paper by Rittel and Webber about optimism in my introductory lecture.

“Planning and the emerging policy sciences are among the more optimistic of those professions. Their representatives refuse to believe that planning for betterment is impossible, however grave their misgivings about the appropriateness of past and present modes of planning. They have not abandoned the hope that the instruments of perfectability can be perfected.”

Horst W.J. Rittel and Melvin M. Webber, “Dilemmas in a general theory of planning,” Policy Sciences 4, 1973.

Operations research is one part planning: we build math models to inform decisions. We do this because we believe we can make a difference. And we believe we can make a difference because we are inherently optimistic.

Do you agree that operations research is optimistic?

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

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:

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:

• graph coloring problems over the holidays