Research Statement

Vision

The 21^st century poses enormous challenges as our aging society faces global competition and an increasing shortage of natural resources. Computer science is called to play a leading role in increasing our operational efficiency so that we can maintain our standard of living with a smaller workforce, using less energy and raw material, and putting less strain on the environment.

After more than 60 years of research, algorithmic computer science can offer a lot to help saving. However, the main impact of computational optimization support is currently limited to large companies in few core application areas such as steel production and the transportation industry. Specialized algorithmic solutions have shown to be extremely successful in these domains. While the algorithmic technologies that have been developed are by no means specific to the current areas of application, the main obstacle for a broader realization of their vast potential is largely due to the lacking ease of use.

Therefore, the objective of my work is to develop techniques that allow general computer scientists and non-optimization experts to exploit optimization power efficiently.

Intellectual Challenges

To increase the accessibility of computational optimization support, we need to facilitate the modeling process, devise robust solvers which gracefully handle even ill-modeled problems with high efficiency, and provide a high level of automation. To achieve these goals, we can build on a wealth of techniques which have been developed in three historically separate research areas: artificial intelligence, operations research, and algorithm theory. My research hybridizes ideas developed in all three communities. Especially the integration of methods from approximation theory, mathematical programming, and constraint programming has proven very successful in boosting the solution efficiency for discrete feasibility and optimization problems such as airline crew scheduling, scientific experiment design, automatic recording, resource constrained shortest paths, graph partitioning, and capacitated network design.

By nature, my work spans over all parts of the value-added chain: starting from the formal modeling of a real-world problem, via the identification of critical structures and the development of provably efficient subroutines that are then combined to form a complete solution algorithm, all the way to its prototype implementation and calibration. A key part of my work is then the abstraction and generalization of originally problem-tailored approaches to standard solution methods that facilitate algorithm design and algorithm engineering for constraint satisfaction and constrained optimization. Theoretical abstraction and generalization allows my work to gain significance beyond the current problem at hand while prototyping enables it to gain a direct impact for a concrete problem, with the additional benefit of having the unfiltered feedback from a practical evaluation. Often, during the process of implementation, new ideas and problems arise that stimulate additional theoretical research, which transforms the entire process into a value-added helix rather than a one-way chain only.

Past Impact and Future Prospects

Central themes of my research program are 1) Symmetry Breaking - development of efficient symmetry breaking methods, 2) Symbolic Reasoning - development of provably efficient filtering algorithms for important substructures of hard combinatorial problems, 3) Hybrid Methods - exploitation of problem structure in combination with tight global bounds provided by linear programming and approximation algorithms, 4) Search and Algorithm Configuration - boosting average-case performance.

(1) Symmetry Breaking

Symmetries can give rise to severe problems for exact and heuristic search algorithms as equivalent search regions are unnecessarily being explored more than just once. Especially in combinatorial design, symmetric search regions are often explored many millions of times. We introduced a simple method that breaks the symmetries of a problem during the search procedure [2]. Our technique, known as Symmetry Breaking by Dominance Detection (SBDD), is widely regarded as the most efficient dynamic symmetry breaking technique and is one of the most highly cited methods in constraints in this decade. At IJCAI 2005, one of the two highly selective flagship conferences on AI research, we showed that breaking arbitrary symmetries is intractable, while for special cases we were able to devise efficient symmetry breaking approaches [17]. In particular, SBDD allowed us to devise the first ever efficient symmetry breaking technique for problems that exhibit both piecewise variable and value symmetry.

While our hope was that this method would facilitate the handling of symmetries for practitioners working on discrete algorithms, meanwhile the research community has taken our method much further by coupling it with a group theory module that extracts the symmetries automatically out of some examples it is provided with. Moreover, based on our work on SBDD we were able to derive a very easy-to-use static symmetry breaking method for problems with piecewise variable and value symmetries. The latter can be detected automatically by a static analysis of a given constraint program. In combination with a simple restarted search approach, this method marks the current state-of-the-art for piecewise symmetric constraint satisfaction problems [3]. This paper received a best paper nomination at CP 2008, the leading international conference on constraint programming.

My work on symmetry breaking continues with the objective to provide the algorithmic foundations for the development of general solvers that allow even inexperienced users to handle problems with symmetries without even knowing that these pose a great challenge for systematic solvers.

(2) Symbolic Reasoning – Global Constraints

When looking at constrained optimization problems, we often find that they can be viewed as a combination of well-known substructures that constitute the problem as a whole. To make the statement of an optimization problem easier, we would like to be able to model a problem as a conjunction of such natural substructures. While in mathematical programming the user is forced to disintegrate a possibly well-structured optimization problem into a set of linear inequalities, constraint programming offers the freedom to provide higher order, so called “global constraints.” While this facilitates the modeling process significantly, it also offers the possibility to improve the solution efficiency by exploiting special knowledge on the underlying structures of a problem.

To provide a set of building blocks that capture frequent substructures of real-world combinatorial problems, I developed the state-of-the-art filtering routines for weighted bipartite matching, weighted stable sets on interval graphs, context-free grammars, shortest-paths, and knapsacks [4,6,11,12,15]. Since complete filtering is frequently intractable for important structures, I introduced new notions of relaxed and approximated consistency which allow us to classify rigorously the filtering effectiveness of incomplete polynomial-time filtering algorithms. Moreover, to achieve a more realistic assessment of the practical performance of filtering algorithms, I made a case for amortized and expected-case analyses of filtering algorithms. For knapsack constraints, we developed the first expected sub-linear time algorithm which outperforms the old state-of-the-art by more than two orders of magnitude in practice [6]. Reflecting that they have now become the new standard in constraints research, at CP 2009, in collaboration with Chris Jefferson, I was invited to give a tutorial on amortized and expected-case complexity analyses for filtering algorithms. My work on global constraints is also highly cited, among others in the standard CP reference, the Handbook of Constraint Programming by Rossi et al.

(3) Hybrid Methods - Cost-Based Filtering

When exploiting the substructures of a problem, we are facing the problem that looking at one substructure at a time does not provide a global view on the entire problem, which is essential for the computation of tight bounds on the objective function in optimization problems. To overcome this problem, we developed two techniques that allow combining local filtering methods with tight global bounds on the objective. We achieve this combination by applying decomposition methods from operations research, column generation and Lagrangian relaxation [9,14]. CP-based column generation has become the standard framework for solving scheduling problems with complex side constraints which occur frequently in practice, e.g., in airline crew scheduling. For CP-based Lagrangian relaxation I was able to prove a surprising theoretical result that shows that stronger filtering effectiveness is generally achieved by considering sub-optimal Lagrangian relaxations [9]. Both frameworks are prominently cited in the two standard reference books on the integration of CP and OR by Hooker and Milano.

An intellectually very stimulating line of my research regards the use of approximation within exact optimization approaches. While the theory of approximation algorithms is very rich and also most beautiful, surprisingly little use is being made of them in practice: either because people are interested in exact solutions only, or because some polynomial-time heuristics perform better on structured real-life instances, even though they do not come with a performance guarantee. This situation changes when we look at the substructures of a problem that we try to solve to optimality. Thinking of the knapsack problem as an example, state-of-the-art methods work very efficiently by focusing on an extensible core problem, and approximation algorithms are not used at all in practice. If we assume, however, that the capacity constraint on some resource is only one part of the optimization problem that we are trying to solve, the situation changes fundamentally and in favor of approximation algorithms. While the specialized knapsack solvers fail to work in the presence of additional constraints, and while heuristics do not allow us to perform cost-based filtering because they do not provide any performance guarantee, approximation algorithms can be used to provide provably tight bounds for cost-based filtering on the knapsack substructure. For knapsacks I found that performing filtering on top of computing a provably tight bound on the objective can be done in amortized linear time [11]. Another filtering algorithm that achieves approximated consistency is based on a new fully polynomial-time approximation scheme for automatic recording that I developed. In [8] I was able to show that this algorithm can lead to speed-ups of more than three orders of magnitude when solving the automatic recording problem.

(4) Search and Algorithm Configuration

Practically efficient combinatorial algorithms embed inference techniques, like the ones mentioned in the three sections above, in a search environment. Since inference is usually made provably polynomial, it is only the (exponential) search which enables the approach to solve NP-hard problems. Not surprisingly, theoretical analyses of the computational complexity of practically efficient search algorithms are very rare. In [16] we studied binary searches with higher costs for unsuccessful trials and were able to show that this scenario allows us to devise a provably optimal search strategy. The result was published at CP 2008 where it was nominated for the best research paper award.

In an effort to boost the average-case performance of search algorithms, when our ability to reason deterministically about a formerly unexplored search region is exhausted, we can still apply probabilistic inference techniques to guide the systematic search of deterministic solvers for combinatorial problems. The hope is that statistics can be exploited to learn offline or during the search process how the search can be organized better. At AAAI 2006, the other international flagship conference on artificial intelligence, we demonstrated empirically that learning during search can dramatically boost the average-case performance of state-of-the-art solvers [13]. This year, we developed a new local search meta-heuristic, dialectic search, which is motivated by empirically observed statistical features such as fitness-distance correlations and so-called “global valley structures” [5]. For set covering, one of the most important and also most studied combinatorial optimization problems, our approach outperforms the old state-of-the-art, which had been uncontested for over a decade, by more than one order of magnitude.

Search can also be used to boost other search algorithms. Algorithm configuration and parameter tuning are laborious tasks and represent a significant obstacle for non-experts when developing proprietary solution approaches for their optimization problems. In [1] we devised a new genetic algorithm for algorithm configuration which uses two genders for search space exploitation and exploration. In terms of tuning quality, our approach vastly outperforms existing configurators by up to 45%. Moreover, we recently developed an approach for instance-specific parameter tuning which received a nomination for best paper at ICTAI 2009 [7].

From an intellectual perspective, while our understanding of inference techniques is very mature, it is very reasonable to assume that the most significant future performance gains of combinatorial solvers will be based on adaptive search algorithms. The potential for improvement by boosting average-case search performance are tremendous. This makes this line of research extremely promising and it is a major focus of my future research agenda.

An Exciting Time for Constrained Optimization

While three different communities – artificial intelligence, operations research, and algorithm theory – have been working independently on the same or related problems in the past, they have now come to exchange their experience and to combine solution methods. As one result, modeling real-life problems has become much easier, and solution approaches have become less specialized and more robust. Our work on global constraints and their linking via standard decomposition approaches are examples for this trend. At the same time, by using hybrid approaches, for many problems we have been able to boost the solution power by several orders of magnitude.

With no doubt, the facilitated use of increasing optimization power will have a major impact on the entire society. While most computers that are sold today are used to provide access to the web, for leisure, to manage large amounts of data, or just to edit texts, the potential of becoming a valuable decision support tool in the private as well as the professional sector already exists today. It is a pressing task for computer science to make it widely accessible at last.

References

[1] Carlos Ansotegui Gil, Meinolf Sellmann, Kevin Tierney. A Gender-Based Genetic Algorithm for the Automatic Configuration of Solvers. 15^th International Conference on the Principles and Practice of Constraint Programming (CP), Springer LNCS 5732, pp. 142-157, 2009.

[2] Torsten Fahle, Stefan Schamberger, and Meinolf Sellmann. Symmetry Breaking. 7^th International Conference on the Principles and Practice of Constraint Programming (CP), Springer LNCS 2239, pp. 93-107, 2001.

[3] Daniel Heller, Aurojit Panda, Meinolf Sellmann, and Justin Yip. Model Restarts for Static Symmetry Breaking. 14^th International Conference on the Principles and Practice of Constraint Programming (CP), Springer LNCS 5202, pp. 539-544 [nominated for the best research paper award]

[4] Serdar Kadioglu and Meinolf Sellmann. Grammar Constraints. Constraints. To appear, 2009.

[5] Serdar Kadioglu and Meinolf Sellmann. Dialectic Search. 15^th International Conference on the Principles and Practice of Constraint Programming (CP), Springer LNCS 5732, pp. 486-500, 2009.

[6] Irit Katriel, Meinolf Sellmann, Eli Upfal, and Pascal Van Hentenryck. Propagating Knapsack Constraints in Sublinear Time. 22^nd National Conference on Artificial Intelligence (AAAI), pp.231-236, 2007.

[7] Yuri Malitsky and Meinolf Sellmann. Stochastic Offline Programming. Accepted at ICTAI, 2009. [nominated for the best research paper award]

[8] Meinolf Sellmann. Approximated Consistency for the Automatic Recording Constraint. Computers and Operations Research, Vol. 36(8), pp. 2341-2347, 2009.

[9] Meinolf Sellmann. Theoretical Foundations of CP-based Lagrangean Relaxation. 10^th International Conference on the Principles and Practice of Constraint Programming (CP), LNCS 3258, pp. 634-647, 2004.

[10] Meinolf Sellmann. The Practice of Approximated Consistency for Knapsack Constraints. 19^th National Conference on Artificial Intelligence (AAAI), AAAI Press, pp. 179-184, 2004.

[11] Meinolf Sellmann. Approximated Consistency for Knapsack Constraints. 9^th International Conference on the Principles and Practice of Constraint Programming (CP), Springer LNCS 2833, pp. 679-693, 2003.

[12] Meinolf Sellmann. An Arc-Consistency Algorithm for the Minimum Weight All Different Constraint. 8^th International Conference on the Principles and Practice of Constraint Programming (CP), Springer LNCS 2470, pp. 744-749, 2002.

[13] Meinolf Sellmann and Carlos Ansotegui. Disco-Novo-GoGo: Integrating Local Search and Complete Search with Restarts. 21^st National Conference on Artificial Intelligence (AAAI), pp. 1051-1056, 2006.

[14] Meinolf Sellmann and Torsten Fahle. Constraint Programming Based Lagrangean Relaxation for the Automatic Recording Problem. Annals of Operations Research (AOR), Vol. 118, pp. 17-33, 2003.

[15] Meinolf Sellmann, Thorsten Gellermann, Robert Wright. Cost-Based Filtering for Shorter Path Constraints. Constraints. Vol. 12(2), pp. 207-238, 2007.

[16] Meinolf Sellmann and Serdar Kadioglu. Dichotomic Search Protocols. 14^th International Conference on the Principles and Practice of Constraint Programming (CP), Springer LNCS 5202, pp. 251-265, 2008. [nominated for the best research paper award]

[17] Meinolf Sellmann and Pascal Van Hentenryck. Structural Symmetry Breaking. 19^th International Joint Conference on Artificial Intelligence (IJCAI), pp. 298-303, 2005.