4 Presentations

• 
  10:30 AM - 10:55 AM

  Activity-Based Search for Black-Box Constraint Programming Solvers

  • Laurent Michel, presenter, University of Connecticut
  • Pascal Van Hentenryck, National ICT Australia

  Robust search procedures are a central component in the design of black-box constraint-programming solvers. This paper proposes activity-based search, the idea of using the activity of variables during propagation to guide the search. Activity-based search was compared experimentally to impact-based search and the WDeg heuristics. Experimental results on a variety of benchmarks show that activity-based search is more robust than other heuristics and may produce significant improvements in performance.

• 
  10:55 AM - 11:20 AM

  Counting-Based Search: Branching Heuristics for Constraint Satisfaction Problems

  • Gilles Pesant, presenter, Polytechnique Montréal

  Designing a search heuristic for constraint programming that is reliable across problem domains has been an important research topic in recent years. This talk concentrates on one family of candidates: counting-based search. Such heuristics seek to make branching decisions that preserve most of the solutions by determining what proportion of solutions to each individual constraint agree with that decision. Whereas most generic search heuristics in constraint programming rely on local information at the level of the individual variable, our search heuristics are based on more global information at the constraint level. We first sketch the algorithmic developments necessary to equip constraints with counting. We then present a comparative empirical analysis based on several problem domains ranging from well-established benchmark puzzles to rostering and sport scheduling.

• 
  11:20 AM - 11:45 AM

  Guiding Combinatorial Search with UCT

  • Ashish Sabharwal, presenter, IBM Watson Research Center
  • Horst Samulowitz, IBM Watson Research Center
  • Chandra Reddy, IBM Watson Research Center

  We propose a new approach for search tree exploration in the context of combinatorial optimization, specifically Mixed Integer Programming (MIP), that is based on UCT, an algorithm for the multiarmed bandit problem designed for balancing exploration and exploitation in an online fashion. UCT has recently been highly successful in game tree search. We discuss the differences that arise when UCT is applied to search trees as opposed to bandits or game trees, and provide initial results demonstrating that the performance of even a highly optimized
  state-of-the-art MIP solver such as CPLEX can be boosted using UCT’s guidance on a range of problem instances.

• 
  11:45 AM - 12:10 PM

  Dynamic Instance-Specific Algorithm Tuning for Set Partitioning

  • Meinolf Sellmann, presenter, IBM Research

  We present a dynamic branching scheme for set partitioning problems. The idea is to trace features of the underlying MIP model and to base search decisions on the features of the current subproblem to be solved. We show how such a system can be trained efficiently by introducing minimal learning bias that traditional model-based machine learning approaches rely on. Experiments on a highly heterogeneous collection of set partitioning instances show significant gains over dynamic search guidance in Cplex as well as instancespecifically tuned pure search heuristics.