Toy-level solver implementation of various problems including SAT, SMT, Max-SAT, PBSPBO (Pseudo Boolean SatisfactionOptimization), MILP (Mixed Integer Linear Programming) and non-linear real arithmetic.


Keywords
bsd3, constraints, formal-methods, library, logic, optimisation, optimization, program, smt, theorem-provers, Propose Tags, Skip to Readme, Index, Quick Jump, ToySolver.Arith.BoundsInference, ToySolver.Arith.CAD, ToySolver.Arith.ContiTraverso, ToySolver.Arith.Cooper, ToySolver.Arith.Cooper.Base, ToySolver.Arith.Cooper.FOL, ToySolver.Arith.DifferenceLogic, ToySolver.Arith.FourierMotzkin, ToySolver.Arith.FourierMotzkin.Base, ToySolver.Arith.FourierMotzkin.FOL, ToySolver.Arith.FourierMotzkin.Optimization, ToySolver.Arith.LPUtil, ToySolver.Arith.MIP, ToySolver.Arith.OmegaTest, ToySolver.Arith.OmegaTest.Base, ToySolver.Arith.Simplex, ToySolver.Arith.Simplex.Simple, ToySolver.Arith.Simplex.Textbook, ToySolver.Arith.Simplex.Textbook.LPSolver, ToySolver.Arith.Simplex.Textbook.LPSolver.Simple, ToySolver.Arith.Simplex.Textbook.MIPSolver.Simple, ToySolver.Arith.VirtualSubstitution, ToySolver.BitVector, ToySolver.BitVector.Base, ToySolver.BitVector.Solver, ToySolver.Combinatorial.BipartiteMatching, ToySolver.Combinatorial.HittingSet.DAA, ToySolver.Combinatorial.HittingSet.FredmanKhachiyan1996, ToySolver.Combinatorial.HittingSet.GurvichKhachiyan1999, ToySolver.Combinatorial.HittingSet.HTCBDD, ToySolver.Combinatorial.HittingSet.InterestingSets, ToySolver.Combinatorial.HittingSet.MARCO, ToySolver.Combinatorial.HittingSet.SHD, ToySolver.Combinatorial.HittingSet.Simple, ToySolver.Combinatorial.HittingSet.Util, ToySolver.Combinatorial.Knapsack.BB, ToySolver.Combinatorial.Knapsack.DPDense, ToySolver.Combinatorial.Knapsack.DPSparse, ToySolver.Combinatorial.SubsetSum, ToySolver.Converter, ToySolver.Converter.Base, ToySolver.Converter.GCNF2MaxSAT, ToySolver.Converter.MIP2PB, ToySolver.Converter.MIP2SMT, ToySolver.Converter.NAESAT, ToySolver.Converter.ObjType, ToySolver.Converter.PB, ToySolver.Converter.PB2IP, ToySolver.Converter.PB2LSP, ToySolver.Converter.PB2SMP, ToySolver.Converter.PBSetObj, ToySolver.Converter.QBF2IPC, ToySolver.Converter.QUBO, ToySolver.Converter.SAT2KSAT, ToySolver.Converter.SAT2MIS, ToySolver.Converter.SAT2MaxCut, ToySolver.Converter.SAT2MaxSAT, ToySolver.Converter.Tseitin, ToySolver.Data.AlgebraicNumber.Complex, ToySolver.Data.AlgebraicNumber.Real, ToySolver.Data.AlgebraicNumber.Root, ToySolver.Data.AlgebraicNumber.Sturm, ToySolver.Data.BoolExpr, ToySolver.Data.Boolean, ToySolver.Data.DNF, ToySolver.Data.Delta, ToySolver.Data.FOL.Arith, ToySolver.Data.FOL.Formula, ToySolver.Data.IntVar, ToySolver.Data.LA, ToySolver.Data.LA.FOL, ToySolver.Data.LBool, ToySolver.Data.OrdRel, ToySolver.Data.Polynomial, ToySolver.Data.Polynomial.Factorization.FiniteField, ToySolver.Data.Polynomial.Factorization.Hensel, ToySolver.Data.Polynomial.Factorization.Hensel.Internal, ToySolver.Data.Polynomial.Factorization.Integer, ToySolver.Data.Polynomial.Factorization.Kronecker, ToySolver.Data.Polynomial.Factorization.Rational, ToySolver.Data.Polynomial.Factorization.SquareFree, ToySolver.Data.Polynomial.Factorization.Zassenhaus, ToySolver.Data.Polynomial.GroebnerBasis, ToySolver.Data.Polynomial.Interpolation.Hermite, ToySolver.Data.Polynomial.Interpolation.Lagrange, ToySolver.EUF.CongruenceClosure, ToySolver.EUF.EUFSolver, ToySolver.EUF.FiniteModelFinder, ToySolver.FileFormat, ToySolver.FileFormat.Base, ToySolver.FileFormat.CNF, ToySolver.Graph.Base, ToySolver.Graph.MaxCut, ToySolver.Graph.ShortestPath, ToySolver.Internal.Data.IOURef, ToySolver.Internal.Data.IndexedPriorityQueue, ToySolver.Internal.Data.PriorityQueue, ToySolver.Internal.Data.SeqQueue, ToySolver.Internal.Data.Vec, ToySolver.Internal.ProcessUtil, ToySolver.Internal.TextUtil, ToySolver.Internal.Util, ToySolver.QBF, ToySolver.QUBO, ToySolver.SAT, ToySolver.SAT.Encoder.Cardinality, ToySolver.SAT.Encoder.Cardinality.Internal.Naive, ToySolver.SAT.Encoder.Cardinality.Internal.ParallelCounter, ToySolver.SAT.Encoder.Cardinality.Internal.Totalizer, ToySolver.SAT.Encoder.Integer, ToySolver.SAT.Encoder.PB, ToySolver.SAT.Encoder.PB.Internal.Adder, ToySolver.SAT.Encoder.PB.Internal.BDD, ToySolver.SAT.Encoder.PB.Internal.Sorter, ToySolver.SAT.Encoder.PBNLC, ToySolver.SAT.Encoder.Tseitin, ToySolver.SAT.ExistentialQuantification, ToySolver.SAT.Formula, ToySolver.SAT.MUS, ToySolver.SAT.MUS.Enum, ToySolver.SAT.MUS.Types, ToySolver.SAT.PBO, ToySolver.SAT.PBO.BC, ToySolver.SAT.PBO.BCD, ToySolver.SAT.PBO.BCD2, ToySolver.SAT.PBO.Context, ToySolver.SAT.PBO.MSU4, ToySolver.SAT.PBO.UnsatBased, ToySolver.SAT.Printer, ToySolver.SAT.Solver.CDCL, ToySolver.SAT.Solver.CDCL.Config, ToySolver.SAT.Solver.MessagePassing.SurveyPropagation, ToySolver.SAT.Solver.SLS.ProbSAT, ToySolver.SAT.Solver.SLS.UBCSAT, ToySolver.SAT.Store.CNF, ToySolver.SAT.Store.PB, ToySolver.SAT.TheorySolver, ToySolver.SAT.Types, ToySolver.SDP, ToySolver.SMT, ToySolver.Text.SDPFile, ToySolver.Version, ToySolver.Wang, More info, toysolver-0.8.1.tar.gz, browse, Package description, revised, metadata revisions, Package maintainers, MasahiroSakai, edit package information , 0.1.0, 0.2.0, 0.3.0, INSTALL.md, ersatz-toysat, ersatz, satchmo-toysat, satchmo, bytestring-encoding, data-interval, extended-reals, finite-field, MIP, OptDir, pseudo-boolean, sign, algorithms, mathematical-programming, sat-solver, smt-solver, theorem-prover
License
BSD-3-Clause
Install
cabal install toysolver-0.8.1

Documentation

toysolver

License Join the chat at https://gitter.im/msakai/toysolver

Hackage: Hackage Hackage Deps Hackage CI

Dev: Build Status (AppVeyor) Build Status (GitHub Actions) Coverage Status

It provides solver implementations of various problems including SAT, SMT, Max-SAT, PBS (Pseudo Boolean Satisfaction), PBO (Pseudo Boolean Optimization), MILP (Mixed Integer Linear Programming) and non-linear real arithmetic.

In particular it contains moderately-fast pure-Haskell SAT solver 'toysat'.

Installation

See INSTALL.md.

Usage

This package includes several commands.

toysolver

Arithmetic solver for the following problems:

  • Mixed Integer Liner Programming (MILP or MIP)
  • Boolean SATisfiability problem (SAT)
  • PB
    • Pseudo Boolean Satisfaction (PBS)
    • Pseudo Boolean Optimization (PBO)
    • Weighted Boolean Optimization (WBO)
  • Max-SAT families
    • Max-SAT
    • Partial Max-SAT
    • Weighted Max-SAT
    • Weighted Partial Max-SAT
  • Real Closed Field

Usage:

toysolver [OPTION...] [file.lp|file.mps]
toysolver --lp [OPTION...] [file.lp|file.mps]
toysolver --sat [OPTION...] [file.cnf]
toysolver --pb [OPTION...] [file.opb]
toysolver --wbo [OPTION...] [file.wbo]
toysolver --maxsat [OPTION...] [file.cnf|file.wcnf]

-h  --help           show help
-v  --version        show version number
    --solver=SOLVER  mip (default), omega-test, cooper, cad, old-mip, ct

toysat

SAT-based solver for the following problems:

  • SAT
    • Boolean SATisfiability problem (SAT)
    • Minimally Unsatisfiable Subset (MUS)
    • Group-Oriented MUS (GMUS)
  • PB
    • Pseudo Boolean Satisfaction (PBS)
    • Pseudo Boolean Optimization (PBO)
    • Weighted Boolean Optimization (WBO)
  • Max-SAT families
    • Max-SAT
    • Partial Max-SAT
    • Weighted Max-SAT
    • Weighted Partial Max-SAT
  • Integer Programming (all variables must be bounded)

Usage:

toysat [file.cnf|-]
toysat --sat [file.cnf|-]
toysat --mus [file.gcnf|file.cnf|-]
toysat --pb [file.opb|-]
toysat --wbo [file.wbo|-]
toysat --maxsat [file.cnf|file.wcnf|-]
toysat --lp [file.lp|file.mps|-]

PB'12 competition result:

  • toysat placed 2nd in PARTIAL-BIGINT-LIN and SOFT-BIGINT-LIN categories
  • toysat placed 4th in PARTIAL-SMALLINT-LIN and SOFT-SMALLINT-LIN categories
  • toysat placed 8th in OPT-BIGINT-LIN category

toysmt

SMT solver based on toysat.

Usage:

toysmt [file.smt2]

Currently only QF_UF, QF_RDL, QF_LRA, QF_UFRDL and QF_UFLRA logic are supported.

toyfmf

SAT-based finite model finder for first order logic (FOL).

Usage:

toyfmf [file.tptp] [size]

toyconvert

Converter between various problem files.

Usage:

toyconvert -o [outputfile] [inputfile]

Supported formats:

  • Input formats: .cnf .wcnf .opb .wbo .gcnf .lp .mps
  • Output formats: .cnf .wcnf .opb .wbo .lsp .lp .mps .smp .smt2 .ys

Bindings

Spin-off projects and packages