2022 Optimization Days
HEC Montréal, Québec, Canada, 16 — 18 May 2022
TA3 - Constraint Programming
May 17, 2022 10:30 AM – 12:10 PM
Location: Procter & Gamble (green)
Chaired by Gilles Pesant
4 Presentations
-
10:30 AM - 10:55 AM
Practically Uniform Solution Sampling in Constraint Programming
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.
-
10:55 AM - 11:20 AM
Peel-and-Bound: Generating Stronger Relaxed Bounds with Multivalued Decision Diagrams
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.
-
11:20 AM - 11:45 AM
Exploiting Model Entropy to Make Branching Decisions in Constraint Programming
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.
-
11:45 AM - 12:10 PM
Acquiring Maps of Interrelated Conjectures on Sharp Bounds
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.