Overview

At the frontier of Operations Research, Algorithms, and Constraint Programming, my research focuses on hard combinatorial feasibility and optimization problems as they arise in the context of real-world applications. I am especially interested in the integration of methods from mathematical programming, approximation theory, and constraint propagation, which has proven very successful in boosting the solution efficiency for discrete feasibility and optimization problems. While an important aim for me is to provide actual software systems that can tackle real-world applications efficiently, 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 is a key part of my work. My main contributions to this line of research were:

• Symmetry Breaking
  • Invented Symmetry Breaking by Dominance Detection (SBDD) and Structural Symmetry Breaking (SSB). SBDD is one of the most cited papers in CP in this decade.
  • Presented the first polynomial method for breaking piecewise variable and value symmetry simultaneously at IJCAI'05.
  • Proposed an integration of static symmetry breaking with restarts at the model level. This method defines the state-of-the-art for breaking piecewise symmetry, outperforming competing approaches by one order of magnitude. (Best paper nomination CP'08)

• Global Constraints
  • Knapsack Constraints: Introduced relaxed and approximate consistency notions for NP-hard constraints to enable tractable filtering while rigorously characterizing filtering effectiveness. Pushed the limitations of traditional filtering complexity studies by introducing amortized and expected-case analysis. Developed the first expected sub-linear time filtering algorithm.
  • Shorter Paths
  • Automatic Recording, and
  • Context-free Grammar Constraints: Developed the fastest memory efficient incremental filtering algorithm to date. (Invited for special issue on outstanding papers at CP'06)

• Integration of CP and OR
  • CP-based Column Generation: Has become the standard framework for crew scheduling problems with complex side constraints.
  • CP-based Lagrangian Relaxation
  • Proposed linearizations of binary constraint networks and grammar constraints with no LP-IP gap.

• Search
  • Dialectic Search: New local search meta-heuristic. Used to define a new state-of-the-art for Set Covering, outperforming the formerly best algorithm by an order of magnitude.
  • Biased Binary Search: Rigorously proved a simple formula for chosing search bias optimally. (Best paper nomination CP'08)
  • Streamlined Constraint Reasoning

• Algorithm Configuration
  • Introduced a gender-based genetic algorithm which significantly outperforms the formerly best configurator.
  • Stochastic Offline Programming: Introduced the idea of instance-specific parameter tuning. (Best paper nomination ICTAI'09)

• Applications
  • Set Covering
  • Airline Crew Scheduling
  • Capacitated Network Design
  • Resource Constrained Shortest Paths
  • Experiment Design
  • Social Golfers
  • Automatic Recording, and
  • Graph Partitioning