How msakai/toysolver works
Main Components
• Command-Line Front-Ends: These include the entry points found in the “app” directory such as toysolver (arithmetic-based), toysat (SAT-based), toysmt (SMT solver built on toysat), toyfmf (finite model finder), and toyconvert (file format converter). Each provides a unique interface for various problem types.
• Solver Library Modules: The “src/ToySolver” directory encapsulates the core solver functionalities. For example:
– Arithmetic and optimization modules (found under “src/ToySolver/Arith”) for MILP, linear programming (Simplex, FourierMotzkin, etc.), OmegaTest, and others.
– SAT solving modules (under “src/ToySolver/SAT”) that implement different encoding strategies (Tseitin, cardinality encoders, PB encoding) and solver strategies such as CDCL and SLS.
– SMT and Boolean modules (e.g., “src/ToySolver/SMT”, “src/ToySolver/BitVector”) that extend SAT capabilities.
– Data and conversion libraries (under “src/ToySolver/Data” and “src/ToySolver/Converter”) that handle input problem formats, algebraic numbers, boolean expressions, and file format conversions.
• Support and Utility Components: This includes internal utility functions (found in “src/ToySolver/Internal”), file format parsing (“src/ToySolver/FileFormat”), and graph/combinatorial logic for problems like Max Cut and Knapsack.
• Testing & Benchmarks: The “test” directory and “benchmarks” folder both serve to validate and evaluate the various algorithms across a range of input formats.
Relationships and Interactions
• The CLI front-ends (toysolver, toysat, etc.) are the user interfaces that accept input files (in formats such as .cnf, .lp, .mps, etc.) and then route these inputs to appropriate solver libraries.
• The input files are parsed by FileFormat modules. If conversions are needed (e.g., between CNF and OPB or LP formats), the Converter modules are used.
• The parsed input is then processed by the appropriate solver engine (arithmetic, SAT, SMT, etc.) that is implemented in the corresponding submodules (Arith, SAT, etc.).
• The solvers use several common utility modules (Data, Internal, Graph) and leverage shared algorithms for different problem constructs.
• Results are then output back to the user through the command-line, and can also be used by other tools (such as the ersatz-toysat and satchmo-toysat bindings).
Architectural Patterns and Design Principles
• Modularity: There is a clear separation between the CLI layer (in “app”) and the core libraries (in “src/ToySolver”). Each solver category (SAT, SMT, arithmetic) is implemented in its own set of modules.
• Reusability and Functional Purity: Being written in Haskell, much of the code is composed of pure functions and modular components that can be reused across multiple solver tools.
• Layered Architecture: At the top, the front-ends handle user interactions; the middle layers handle parsing, data mapping, and conversion; and the bottom layer contains the core algorithms that perform the actual computation.
• Extensibility: The project is structured so that additional solver paradigms or conversion routines can be easily integrated.
Relevant Technologies and Frameworks
• Haskell and its package management (Stack) are central to the project.
• Integration with C components is visible in the “app/toysat-ipasir” directory (notably ipasir.h, ipasir.c, etc.) for performance-critical SAT solving – indicating a foreign function interface (FFI).
Elements
– CLI Applications: toysolver, toysat, toysmt, toyfmf, toyconvert.
– Core Solver Modules: Arith, SAT, SMT, Combinatorial, Data, Converter.
– Support/Utility Modules: Internal, FileFormat, Graph.
– External Dependencies: Haskell’s runtime, potential C libraries (as seen in toysat-ipasir), and any third-party bindings like ersatz-toysat.
– From input files flowing into the CLI.
– From the CLI to file format parsing and conversion layers.
– From converter modules to the specific solver engines.
– From solver engines back to the CLI output.