toysolver

Assorted decision procedures for SAT, SMT, Max-SAT, PB, MIP, etc https://github.com/msakai/toysolver/

Latest on Hackage:0.5.0

This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow stackage.org to host generated Haddocks.

BSD3 licensed by Masahiro Sakai (masahiro.sakai@gmail.com)

toysolver

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

Build Status Build status Coverage Status Hackage

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

  • unpack
  • cd toysolver
  • cabal install

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 QFUF, QFRDL, QFLRA, QFUFRDL 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

TODO

  • Local search

Changes

0.5.0

  • new solvers: ToySolver.BitVector ToySolver.Combinatorial.BipartiteMatching ToySolver.Combinatorial.HittingSet.DAA ToySolver.Combinatorial.HittingSet.MARCO ToySolver.Arith.DifferenceLogic ToySolver.Graph.ShortestPath * ToySolver.QBF
  • toysat add --init-sp option to initialize variable state using survey propagation allow using UBCSAT when solving PBO/WBO problems
  • toysmt * suport bit-vector logic
  • toyconvert pbconvert and lpconvert were merged into a single command toyconvert add --ksat=NUMBER option to convert to k-SAT formula add --linearlize and --linearizer-pb options add --remove-usercuts option
  • add new modules to ToySolver.Converter ToySolver.Converter.GCNF2MaxSAT ToySolver.Converter.MIP2PB ToySolver.Converter.PBLinearlization ToySolver.Converter.SAT2KSAT
  • ToySolver.SAT introduce type classes for adding constraints ToySolver.SAT.Encoder.Tseitin: add XOR and Full-adder encoder ToySolver.SAT.Encoder.PB: add functionality to encode PB constraint using adder networks and sorting networks ToySolver.SAT.MUS.Enum: add GurvichKhachiyan1999 and MARCO to the MUS enumeration methods implement learning rate based branching heuristics add ToySolver.SAT.ExistentialQuantification add ToySolver.SAT.Store.CNF and ToySolver.SAT.Store.PB implement survey propagation as ToySolver.SAT.MessagePassing.SurveyPropagation
  • Data.MIP parameterize Problem type with coefficient type and use Scientific as default introduce Status type add solution file parsers: ToySolver.Data.MIP.Solution.{CBC,CPLEX,GLPK,Gurobi,SCIP} add solver wrapper modules: ToySolver.MIP.Solver.{CBC,CPLEX,Glpsol,GurobiCl,LPSolve,SCIP}
  • add a QDimacs parser as ToySolver.Text.QDimacs
  • add ToySolver.Text.CNF, ToySolver.Text.QDimacs
  • switch to use megaparsec
  • use clock package for measuring duration
  • add simple numberlink solver sample

0.4.0

  • add experimental SMT (Satisfiablity Modulo Theories) solver 'toysmt', which supports theory of uninterpreted functions and linear real arithmetics.
  • fix toysat to output model in Max-SAT format instead of PB/WBO format when solving Max-SAT problems
  • add experimental getAssumptionsImplications functions to ToySolver.SAT module.
  • add getFixedLiterals to ToySolver.SAT module.
  • use 'mwc-random' package instead of 'random' package.
  • introduce 'Config' data type in ToySolver.SAT to simplify configulation management.
  • add subset-sum problem solver
  • implement backracking and explanation generation in simplex solver and congruence closure solver.

0.3.0

  • split OPB/WBO file library into a serarate 'pseudo-boolean' library.

comments powered byDisqus