4 présentations

• 
  10h30 - 10h55

  Practically Uniform Solution Sampling in Constraint Programming

  • Gilles Pesant, prés., Polytechnique Montréal
  • Claude-Guy Quimper, Université Laval
  • Hélène Verhaeghe, Polytechnique Montréal

  The ability to sample solutions of a constrained combinatorial space has important applications in areas such as probabilistic reasoning and hardware/software verification. A highly desirable property of such samples is that they should be drawn uniformly at random, or at least nearly so. For combinatorial spaces expressed as SAT models, approaches based on universal hashing provide probabilistic guarantees about sampling uniformity. In this presentation we apply that same approach to CP models, for which hashing functions take the form of linear constraints in modular arithmetic. We design an algorithm to generate an appropriate combination of linear modular constraints given a desired sample size. We evaluate empirically the sampling uniformity and runtime efficiency of our approach, showing it to be near-uniform at a fraction of the time needed to draw from the complete set of solutions.

• 
  10h55 - 11h20

  Peel-and-Bound: Generating Stronger Relaxed Bounds with Multivalued Decision Diagrams

  • Isaac Rudich, prés., Polytechnique Montréal
  • Quentin Cappart, Cirrelt
  • Louis-Martin Rousseau, Polytechnique Montréal

  Decision diagrams are an increasingly important tool in cutting-edge solvers for discrete optimization. However, the field of decision diagrams is relatively new, and is still incorporating the library of techniques that conventional solvers have had decades to build. We drew inspiration from the warm-start technique used in conventional solvers to address one of the major challenges faced by decision diagram based methods. Decision diagrams become more useful the wider they are allowed to be, but also become more costly to generate, especially with large numbers of variables. We present a method of peeling off a sub-graph of previously constructed diagrams and using it as the initial diagram for subsequent iterations that we call peel-and-bound. We test the method on the sequence ordering problem, and our results indicate that our peel-and-bound scheme generates stronger bounds than a branch-and-bound scheme using the same propagators, and at significantly less computational cost.

• 
  11h20 - 11h45

  Exploiting Model Entropy to Make Branching Decisions in Constraint Programming

  • Auguste Burlats, prés., Polytechnique Montréal

  Branching decisions have a strong impact on performances in Constraint Programming. Therefore robust and generalizable variable ordering heuristics are an important field of research in the Constraint Programming community. By allowing us to compute marginal distributions for each variable of the model, Belief Propagation also allows us to compute the entropy of each variable. We present two new branching heuristics exploiting entropy. One chooses the variable with the smallest entropy. The other one is inspired by impact-based search and chooses the variable that is supposed to have the strongest impact on the entropy of the model. We also propose a dynamic stopping criterion for iterated belief propagation based on variations in model entropy. We test our heuristics on various constraint satisfaction and optimization problems from XCSP and minizinc benchmarks.

• 
  11h45 - 12h10

  Acquiring Maps of Interrelated Conjectures on Sharp Bounds

  • Nicolas Beldiceanu, IMT Atlantique
  • Jovial Cheukam Ngouonou, prés., Université Laval-IMT Atlantique
  • Rémi Douence, IMT Atlantique
  • Ramiz Gindullin, IMT Atlantique
  • Claude-Guy Quimper, Université Laval

  To automate the discovery of conjectures on combinatorial objects, we introduce the concept of a map of sharp bounds on characteristics of combinatorial objects, that provides a set of interrelated sharp bounds for these combinatorial objects. We then describe a Bound Seeker, a CP-based system, that gradually acquires maps of conjectures. The system was tested for searching conjectures on bounds on characteristics of digraphs: it constructs sixteen maps involving 431 conjectures on sharp lower and upper-bounds on eight digraph characteristics.