Matteo Fischetti ( Padova University)
Title
BRANCHstorming (brainstorming about tree search)
Abstract
Quoting from Wikipedia (http://en.wikipedia.org/wiki/System_dynamics): "System Dynamics is an aspect of systems theory as a method for understanding the dynamic behavior of complex systems. The basis of the method is the recognition that the structure of any system — the many circular, interlocking, sometimes time-delayed relationships among its components — is often just as important in determining its behavior as the individual components themselves. Examples are chaos theory and social dynamics. It is also claimed that because there are often properties-of-the-whole which cannot be found among the properties-of-the-elements, in some cases the behavior of the whole cannot be explained in terms of the behavior of the parts."
No doubts that tree search is a very complex process with its own dynamics, that sometimes behaves as a chaotic system due to its high dependency on the initial conditions.
However, tree search is seldom studied as a whole by the Mathematical Programming community, perhaps because it is often perceived as a shame---we should be able to solve our problems at the root node, don't we? As a matter of fact, its main ingredients (e.g., cut generation and selection) are often studied in vitro---i.e., evaluated "at the root node"--- and then just transplanted in the enumeration body with significant organ-rejection rates.
The study of the properties-of-the-whole of tree search is of course a long-term project. In this talk we will make a mandatory preliminary step by addressing a number of preconceptions about it.
We will start reviewing recent work on the role of erraticism in the design and validation of tree-search algorithms, thus addressing the prejudice that enumeration is a stable mechanism whose performance only depends on how clever we are in designing its single elements.
We will then address a main source of erraticism in a branch-and-bound scheme, namely, the existence of multiple relaxation solutions. In particular, we will comment about the risk of overfitting due to the common practice of uncritically picking one such solution (or just few) for guiding the search.