FORUM

The O.R. Tree

By Leonardo Lopes

O.R. 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 makes it challenging to explain to potential collaborators, sponsors and students what O.R. is and what outcomes to expect from a specific project.

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 terms that classified problems based on how concrete or abstract they were, and conveyed their relationships in a factual, non-judgmental and familiar way.

I spend much of my research time on graphs and trees. So that is where I started. After some work I came up with the tree shown in Figure 1.

a tree full of O.R. problems

Figure 1: A tree full of O.R. problems.

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; and which is likely to contribute to the computational 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 extensive domain considerations, requiring significant amounts of original modeling. A capacitated pickup and delivery problem would fall into this category.
  • A leaf problem is highly specialized, usually with a customer in mind, and includes high levels of detail. Scheduling trucks for FedEx would fall into this category.

Another Set of Related Problems

The problem that inspired these definitions is a branch problem: Udine Timetabling (UTT). It was produced for the 2007 International Timetabling Competition as a simplified version of a leaf problem that the University of Udine must solve every semester. It was simplified from its leaf version to enhance the research-oriented goals of the competition. Going down the tree, UTT adds significant detail to timetabling, a trunk problem, such as room sizes, faculty availability, soft limits on the requirements for student travel, etc. Timetabling, assigning events to slots so that there are no resource conflicts, in turn adds detail, or “wrinkles,” to the graph-coloring problem, a core problem.

During the competition, several heuristics were proposed to solve the problems. Several papers with different formulations addressed by different algorithms and heuristics were subsequently published. The main step of each algorithm or heuristic is to reduce the UTT into one or more interrelated core or root problems (such as an integer program, a graph-coloring problem or a string search amenable to simulated annealing or tabu search).

A Detailed View

The “programmings,” e.g. linear programming, integer programming, semidefinite programming, constraint programming and SAT are all root problems. What all these problems have in common is their extremely abstract nature. The instances of these problems are composed only of strings, variables with domains, algebraic relationships or simple constraints. The analogy to the tree is that they do not have an obvious visualization, and they are structural in the sense that other problems are often reduced to them to build algorithms.

Most problems starting with a “the” are core problems (e.g., the traveling salesman, the graph-coloring problem). The 21 problems in Karp’s original NP-completeness paper are almost all core problems (0-1 IP, 3SAT and of course satisfiability are better classified as root problems). The structure of core problems has been extensively studied in O.R. and computer science. Many specialized algorithms and heuristics exist to solve them and related sub-problems. Because they are so generic, there is much that can be said analytically about trunk and core problems. The analysis of the polyhedral structure of the IP formulations of core problems produces powerful insights. A core problem need not be NP-hard. For example: Lot sizing and shortest path are core problems.

Adding extra constraints or decisions to a core problem (e.g., adding fixed charge considerations to lot sizing) leads to a trunk problem. Some of these considerations can transform an easy problem into a hard one. Some of them appear so often as subproblems in branch and leaf problems, that routines that add information to a search (like cuts derived from strengthening fixed charge networks) can improve practical solver performance. These problems are generally studied less widely than core problems, but their contribution to solvers is similar.

Branch problems add further detail to trunk problems. They usually have enough detail that the main contribution from studying them is how to model complex interactions of processes, or how to build specialized algorithms that produce good results by exploiting special structure. Unlike trunk and core problems, branch problems are usually too specialized to produce generic enough insights that they can be applied to generic solvers. Some branch problems are closer to trunk problems and are thus useful to the discipline in a similar way, while others are very close to leaf problems, and are useful in a completely different way.

Finally, leaf problems are those that are specialized to deal with a specific customer or a specific business process. Usually if there is “green” involved, it is a leaf problem. The field needs leaf problems to breathe. As computing capabilities and the business landscape affects what is practical for O.R. to address, the nature of interesting leaf problems changes as well. It is industry, the military and government – the source of leaf problems – that provides oxygen (dollars, outside interest, innovative applications) to the field. New research questions arise at every level; new products are invented, and new research topics become important, while others wither away in a slow phototropic way.

Is This Taxonomy Useful?

Research methods and expected outcomes for addressing problems from different portions of the tree should be different. Mathematical research is most often the appropriate tool to analyze root and core problems. Branch and leaf problems are not as general and benefit more from a scientific, experimental approach. The fact that they are different doesn’t make them less important relative to each other. Forcing the outcomes of addressing one problem class to match those that are useful to another class hurts the entire field.

The analogy can be taken further still: for the benefits of O.R. to be economically viable, there must be a strong supply of competent modelers, healthy innovation in modeling tools and plenty of published examples of branch problems. These resources are produced mostly in universities. In the absence of a healthy dose of basic research on trunk, core and root problems, the field will be malnourished. The analogy also works the other way. The field is healthier when it values innovation on issues such as IT integration, business process design and the economics of analytics. If they are not supported, the field becomes short of breath.

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.

Leonardo Lopes (leo.lopes@monash.edu) is senior research fellow in the School of Mathematical Sciences at Monash University.