4 Presentations

• 
  10:30 AM - 10:55 AM

  Local Alterations of the Lagrange Multipliers for Enhancing the Filtering of the AtMostNValue constraint

  • Frédéric Berthiaume, presenter, Université Laval
  • Claude-Guy Quimper, Université Laval

  We enriched a Lagrangian Relaxation based algorithm for the AtMostNValue constraint. The enhanced algorithm locally changes the Lagrange multipliers to generate more filtering. We test the algorithm on the dominating queens and the p-median problems. In both, the search space is radically diminished and the solving time also decreased.

• 
  10:55 AM - 11:20 AM

  A path to the automatic generation of global constraints propagators.

  • Jovial Cheukam Ngouonou, presenter, Université Laval-IMT Atlantique
  • Ramiz Gindullin, IMT Atlantique
  • Claude-Guy Quimper, U. Laval, Québec
  • Nicolas Beldiceanu, IMT Atlantique
  • Rémi Douence, IMT Atlantique

  We synthesize filtering algorithms for global constraints based on combinatorial objects. Using the Bound Seeker, we generate relations between the features of combinatorial objects. An algorithm selects those that contribute to the filtering of a constraint. We consider the PARTITION constraint which models how to divide a collection of objects.

• 
  11:20 AM - 11:45 AM

  Hybrid Heuristic Search Algorithms for Domain-Independent Dynamic Programming

  • Yuxiao Chen, presenter, University of Toronto
  • Ryo Kuroiwa, University of Toronto
  • J. Christopher Beck, University of Toronto

  Complete anytime beam search (CABS) is the current state-of-art anytime heuristic search algorithm for solving problems formulated as domain-independent dynamic programming (DIDP) models. CABS finds good feasible solutions quickly, but spends much more time proving optimality through repeatedly expanding the same search nodes. We investigate another heuristic search algorithm: breadth-first heuristic search (BFHS) and prove that BFHS expands fewer nodes than CABS when proving optimality. Moreover, BFHS expands the minimal number of nodes under some reasonable structural assumptions about the search space. We introduce two hybrid algorithms that combine CABS and BFHS: a single-threaded algorithm that runs CABS and switches to BFHS when it appears that a close-to-optimal solution has been found; and a multi-threaded algorithm that runs CABS and BFHS in parallel with communication of bounds. Our experiments show that both hybrid algorithms outperform CABS and BFHS with the same number of threads on solving some DIDP problems.

• 
  11:45 AM - 12:10 PM

  Large Neighbourhood Search for Anytime MaxSAT Solving

  • Randy Hickey, presenter, University of Toronto
  • Fahiem Bacchus, University of Toronto

  Maximum satisfiability (MaxSAT) is a natural encoding for many optimization problems and the utility of anytime MaxSAT solving is becoming increasingly useful in real-world applications. Large Neighbourhood Search (LNS) is a well-known algorithmic paradigm for optimization problems that yields good performance in many domains. We will present the first algorithm that applies the LNS framework to anytime MaxSAT solving and introduce a neighbourhood selection policy that provides good empirical performance. We show that by budgeting some amount of time for LNS, we can improve the performance of multiple state-of-the-art anytime MaxSAT solvers on a wide set of benchmarks, as well as find new solutions for several of the instances. In a follow-up work, we propose to use multiple initial solutions to seed LNS in order to avoid getting stuck in local optima. We then show that this enhancement can significantly improve the performance of LNS in anytime MaxSAT solving and discuss potential directions for future work.