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
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
- CP-based Lagrangian Relaxation
- Proposed linearizations of binary constraint networks and grammar constraints with no LP-IP gap.
- 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)
- Set Covering
- Airline Crew Scheduling
- Capacitated Network Design
- Resource Constrained Shortest Paths
- Experiment Design
- Social Golfers
- Automatic Recording, and
- Graph Partitioning