4
$\begingroup$

I'm studying the Moser-Tardos algorithm, which is often used to efficiently find solutions to satisfiability problems and avoid bad events in probabilistic settings. I’ve read that it’s mainly applied in theoretical computer science, particularly for SAT problems, random constraint satisfaction, and graph theory.

enter image description here

Event $A_i$​ represents a bad event.

Given its theoretical power, my question is: Are there any known cases where the Moser-Tardos algorithm (or its variants) has been applied to solve real-world, practical problems? For example, has it been used in areas like software engineering, logistics, or industry-specific optimizations?

I understand that the Moser-Tardos algorithm works by resampling entire clauses, whereas many heuristic SAT solvers tend to flip only a single variable. Given this difference, has the Moser-Tardos algorithm been practically applied in any real-world SAT solving scenarios?

I'd love to learn about any examples, papers, or projects that showcase its real-world use. Thanks in advance!

Improve this question
$\endgroup$
4
  • $\begingroup$ @EmilJeřábek $A_i$ represents a bad event. Thank you for your insight, I should have clarified that. $\endgroup$
    – Jxb
    Commented Oct 17 at 8:54
  • 2
    $\begingroup$ Yes, in generating combinatorial arrays for testing interactions in large-scale software systems (this is my research area). $\endgroup$
    – Ryan Dougherty
    Commented Oct 17 at 23:56
  • $\begingroup$ @RyanDougherty Thank you for your reply! Could you kindly provide some papers or resources related to this topic? I would really appreciate it because I’m not very familiar with this area. $\endgroup$
    – Jxb
    Commented Oct 18 at 1:30
  • 1
    $\begingroup$ see for example this paper by Sarkar/Colbourn in section 5: arxiv.org/pdf/1606.06730. It has experiments to generate an initial array randomly of size guaranteed by the LLL. $\endgroup$
    – Ryan Dougherty
    Commented Oct 21 at 1:20

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.