Contact Information

Meinolf Sellmann
Manager Department AI for Optimization
Thomas J. Watson Research Center, Yorktown Heights, NY USA
      +1dash914dash945dash1691


Overview

 

I work on decision support algorithms for 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 artificial intelligence (machine learning and constraint programming), 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 the first decade of the new millennium.
    • 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: 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
  • Automatic Algorithm Configuration and Algorithm Portfolios
    • Introduced a gender-based genetic algorithm (GGA) which significantly outperforms the formerly best configurator.
    • Stochastic Offline Programming: Introduced the idea of instance-specific parameter tuning. (Best paper nomination ICTAI'09)
    • Introduced low-bias algorithm portfolios 3S and CSHC which were used to devise portfolios for SAT (winning solvers in International SAT Competitions 2012, 2013, 2014)
    • Developed Instance-Specific Algorithm Configurator (ISAC) which generalizes both algorithm portfolios and algorithm configuration by choosing an algorithm/parametrization with respect to the given input. ISAC was used to devise a MaxSAT portfolio which won 6 out of 11 categories in the 2013 MaxSAT Evaluation.
  • Applications
    • Set Covering
    • Airline Crew Scheduling
    • Capacitated Network Design
    • Resource Constrained Shortest Paths
    • Experiment Design
    • Combinatorial Designs
    • Automatic Recording
    • Graph Partitioning
    • Sensor Placement
    • Pipeline Terminal Scheduling
    • Trade Settlement