Efficient sampling method finds solutions for complex constraint problems
A sampling Lovász Local Lemma
Data Structures and Algorithms
Summary
Finding solutions that satisfy many rules at once can be very tricky when the rules interact in complex ways. The authors provide a new method to randomly pick such solutions almost uniformly when certain mathematical conditions are met about these rules and their dependencies. They build on a recent fast counting technique and give an algorithm that finds these solutions within a guaranteed accuracy in a reasonable amount of time. This helps tackle problems where you want to fairly sample valid configurations without bias.
What this means in practice
- •For optimization engineers: Efficiently generate nearly uniform solutions that meet complex constraints to improve heuristic optimization and randomized methods.
- •For game developers: Create diverse valid level configurations by sampling from constraints with guaranteed fairness and randomness.
Authors
Dimitris Achlioptas
Abstract
We give an approximately uniform sampler for satisfying assignments of constraint satisfaction problems that satisfy $4\mathrm e p(Δ+1)^2\le1$, where $p$ is the largest constraint-violation probability under the uniform product distribution, and $Δ$ is the maximum degree of the dependency graph. The algorithm invokes the recent efficient approximate counting algorithm of Liu, Wang, Yin, Zhang, and Zhou as a subroutine and returns a satisfying assignment sampled within total-variation distance $\varepsilon$ of the uniform distribution in $(n+m/\varepsilon)^{O(kΔ\log D)}$ time, where $n$ and $m$ are the numbers of variables and constraints, $D$ is the common domain size, and $k$ bounds the constraint arity.