SAT-Based Techniques for Lexicographically Smallest Finite Models

Mikolás Janota, Choiwah Chow, João Araújo, Michael Codish, Petr VojtechovskýAAAI 2024 · DOI

TL;DR

This paper introduces a novel SAT-based approach to compute a "lexicographically smallest" canonical form for finite algebraic structures. This canonical form is crucial for mathematicians to easily catalog and compare structures, as isomorphic structures will share the same canonical representation. The authors develop efficient techniques to reduce the number of SAT calls, making this approach practical for real-world algebraic problems.

What Problem Does This Paper Address?

Mathematicians often encounter collections of similar algebraic structures (like groups or semigroups) and need a systematic way to identify and distinguish them. A common method is to assign a unique "canonical form" to each structure such that two structures are considered the same if and only if their canonical forms are identical. This is analogous to how a simplified fraction (e.g., 1/2 instead of 2/4) serves as a canonical form for rational numbers.

The specific canonical form addressed here is the "lexicographically smallest finite model" (lexmin). This involves representing the structure's operation (e.g., a multiplication table) as a long vector and finding an isomorphic structure whose vector representation is the smallest possible when compared lexicographically. While the concept is well-established, efficiently computing this lexmin form, especially for larger structures, has been a significant challenge. The paper aims to bridge this gap by leveraging the power of SAT solvers.

Methods

The core of the paper is a SAT-based algorithm that constructs the lexmin representation gradually. Instead of trying to encode the entire target structure at once, the algorithm builds it cell by cell, row by row.

  1. Explicit Encoding (Initial Idea): The initial thought is to encode the problem as a SAT instance where variables represent the unknown isomorphism and the resulting operation table. This involves generating constraints to ensure the isomorphism is a bijection and that the operations are preserved. However, this approach leads to a very large encoding (O(|D|⁵) clauses), making it impractical.
  2. Gradual Construction (Novel Approach): The paper proposes a more efficient method where the target magma (D, ◊) is constructed incrementally. The algorithm iterates through the cells of the multiplication table (e.g., (1,1), (1,2), ..., (n,n)). For each cell (r, c), it tries to assign a value v such that the resulting magma is an isomorphic copy of the input magma (D, *). This is achieved by encoding the unknown isomorphism f and using the relation r ◊ c = f(f⁻¹(r) * f⁻¹(c)). The algorithm tries values for v starting from the smallest possible, and if a SAT call succeeds, that value is fixed for the cell. This process is repeated until the entire table is filled.
  3. Efficiency Improvements: To tackle the potential for a large number of SAT calls and difficult individual calls, several propagation techniques are introduced:
  4. Budgeting: Each element in the domain is assigned a "budget" representing how many times it can appear in a row/column/table. This budget is decremented as elements are placed, and SAT calls for values that have exhausted their budget are avoided.
  5. Row/Column Invariants: Properties of rows (or columns) that are invariant under isomorphism are calculated. If a row in the target magma is completely filled, its invariant is computed. If this invariant uniquely matches a row in the original magma, the corresponding mapping is fixed (e.g., f(r') = r), which helps prune the search space.
  6. Mid-Row Budgeting Refinement: Budgets are refined even while filling a single row, based on whether the row contains an idempotent.
  7. Upper Bound by Last Value: The value obtained from a successful SAT call provides an upper bound for subsequent searches in that cell, allowing the algorithm to skip checking larger values.
  8. Search Strategies: Modified binary search and linear-unsat-sat strategies are employed to efficiently find the smallest value for each cell.

Datasets

The paper evaluates its approach on randomly generated samples from five algebraic structures: groups, loops, general magmas, quasigroups, and semigroups. They consider structures of orders ranging from 16 to 256. The authors do not introduce new benchmark datasets but rather use standard algebraic structures commonly studied in computational algebra.

Key Insights and Ideas

  • Canonical Forms are Fundamental: The paper strongly emphasizes the importance of canonical forms in mathematics for cataloging, comparing, and understanding algebraic structures.
  • SAT Solvers as General-Purpose Tools: By framing the lexmin problem as a SAT problem, the paper demonstrates the versatility of SAT solvers beyond typical satisfiability checking, extending their reach into computational algebra.
  • Gradual Construction is Key: The shift from an "explicit encoding" to a "gradual construction" approach is crucial for making the problem tractable. Building the solution incrementally, rather than all at once, significantly reduces the complexity of the SAT encoding.
  • Counting is a SAT Bottleneck: The authors correctly identify that counting arguments (like pigeonhole principles) are often difficult for SAT solvers. Their propagation techniques, particularly budgeting and invariant-based pruning, directly address this weakness.
  • Isomorphism Invariants are Powerful: The use of invariants to identify mappings between rows/columns of the original and target magmas is a clever way to prune the search space and reduce SAT calls.

Key Results

The paper presents an ablation study showing the effectiveness of their proposed techniques. The "all enhancements" version of their tool, mlex, significantly outperforms the basic algorithm.

  • The most significant improvements come from budgeting and row identification.
  • The modified binary search strategy also provides a notable speedup.
  • The tool was evaluated on various algebraic structures, demonstrating its applicability.
  • While specific quantitative results (like speedup factors) are presented in the figures (e.g., Figure 2 and 3), the text highlights that the enhancements lead to solving more instances and doing so faster. The figures show that with all enhancements, the tool can solve instances up to order 175 within a reasonable time frame.

Limitations and Future Work

  • Scalability: While the approach is more scalable than previous methods, the problem remains computationally intensive, and the authors acknowledge that it's unlikely to be "computationally easy" in general. The experiments have a timeout of 30 minutes.
  • Generalization: The current implementation primarily supports single binary operations. Extending it to structures with multiple operations or more complex relational structures is a future direction.
  • Integration with CAS: The authors suggest integrating their tool into computer algebra systems (CAS) like GAP for broader usability.
  • More Advanced Propagation: Further research into more sophisticated invariants and propagation techniques is envisioned.
  • Non-isomorphic Structure Enumeration: The techniques could potentially be adapted for enumerating non-isomorphic structures under specific constraints.

Summary updated

BibTeX
@inproceedings{janota2024sat,
  author = {Mikolás Janota and Choiwah Chow and João Araújo and Michael Codish and Petr Vojtechovský},
  title = {{SAT-Based Techniques for Lexicographically Smallest Finite Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i8.28643},
}

Loading related content...

Figure