OR problems are very diverse. Some problems are closely tied to a customer. Others are purely abstract in form. There are problems in every shade in between. This diversity is a great source of strength. At the same time, this diversity sometimes make it challenging to explain to potential students, collaborators and sponsors what OR is.

Rather than distinguish between types of related problems using words like “fundamental”, “applied”, and “real”, which don’t convey anything beyond what the reader wants them to convey, I was looking for more useful terms. Terms that classified problems and conveyed their relationships in a factual, non-judgmental and familiar way.

Given that I spend so much of my research time on graphs and trees, that is where I started. After some work I came up with this tree:

The OR Problem Tree

A summary of the problem classes, with elevator definitions, and related examples, follows:

  • Root problems have no domain-specific form. Integer Programming is an example.
  • A Core problem is one whose form many people are familiar with; whose structure has been extensively studied; which is likely to contribute to the complexity of derived problems. The Traveling Salesperson Problem is such a problem.
  • A Trunk problem adds some domain-specific detail to a core problem, but is still very generic. The Vehicle Routing Problem with Time Windows is an example.
  • A Branch problem is a specialized¬† trunk problem with domain considerations requiring significant amounts of original modeling, often requiring specialized solution procedures. A capacitated pickup and delivery problem would fall into this category.
  • A Leaf problem is highly specialized, usually with a customer in mind, including high levels of detail. Scheduling trucks for Fedex would fall into this category.

The problem in the paper I am working on is a trunk problem: Udine Timetabling. It adds “wrinkles” to the Graph Coloring problem, a core problem. Most problems starting with a “the” are core problems; usually if there is “green” involved, it is a leaf problem.

Obvious other examples include: Metaheuristics as root problems; The Karp 21 as core problems (0-1 IP and 3SAT are probably root problems).

I am curious about whether people think this taxonomy is useful; whether they would suggest changes; and where they think the problems they are working on go on the tree.

Advertisements