The toysolver package

[ Tags: algorithms, benchmark, bsd3, constraints, library, logic, optimisation, optimization, program, theorem-provers ] [ Propose Tags ]

Toy-level implementation of some decision procedures


[Skip to Readme]

Properties

Versions 0.0.2, 0.0.3, 0.0.4, 0.0.4.1, 0.0.5, 0.0.6, 0.1.0, 0.2.0, 0.3.0, 0.4.0
Change log CHANGELOG.markdown
Dependencies array (>=0.4.0.0), base (>=4.6 && <5), bytestring (>=0.9.2.1 && <0.11), bytestring-builder, containers (>=0.5.0), data-default-class, data-interval (>=1.0.1 && <1.3.0), deepseq, exceptions (==0.5 || >=0.6), extended-reals (>=0.1 && <1.0), filepath, finite-field (>=0.7.0 && <0.9.0), ghc-prim, hashable (>=1.1.2.5 && <1.3.0.0), haskeline (==0.7.*), heaps, intern (>=0.9.1.2 && <1.0.0.0), loop (>=0.2.0 && <1.0.0), MemoTrie (<=0.6.2), mtl (>=2.1.2), multiset, mwc-random (>=0.13.1 && <0.14), old-locale, OptDir, parse-dimacs, parsec (>=3.1.2 && <4), prettyclass (>=1.0.0), primes, process (>=1.1.0.2), pseudo-boolean (>=0.1.3.0 && <0.2.0.0), queue, semigroups (>=0.17), sign (>=0.2.0 && <1.0.0), split, stm (>=2.3), template-haskell, temporary (>=1.2), time, toysolver, transformers (>=0.2), transformers-compat (>=0.3), type-level-numbers (>=0.1.1.0 && <0.2.0.0), unbounded-delays, unordered-containers (>=0.2.3 && <0.3.0), vector, vector-space (>=0.8.6) [details]
License BSD3
Author Masahiro Sakai (masahiro.sakai@gmail.com)
Maintainer masahiro.sakai@gmail.com
Category Algorithms, Optimisation, Optimization, Theorem Provers, Constraints, Logic
Bug tracker https://github.com/msakai/toysolver/issues
Source repository head: git clone git://github.com/msakai/toysolver.git
Uploaded Mon Jan 25 13:10:40 UTC 2016 by MasahiroSakai
Updated Mon Oct 3 12:22:18 UTC 2016 by MasahiroSakai to revision 1
Distributions NixOS:0.4.0
Executables pbverify, maxsatverify, pigeonhole, svm2lp, htc, knapsack, nqueens, nonogram, sudoku, pbconvert, lpconvert, toyfmf, toysmt, toysat, toysolver
Downloads 1913 total (16 in the last 30 days)
Rating 0.0 (0 ratings) [clear rating]
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2016-11-16 [all 1 reports]
Hackage Matrix CI

Modules

[Index]

Flags

NameDescriptionDefaultType
forcechar8

set default encoding to char8 (not to use iconv)

DisabledManual
linuxstatic

build statically linked binaries

DisabledManual
buildtoyfmf

build toyfmf command

DisabledManual
buildsampleprograms

build sample programs

DisabledManual
buildmiscprograms

build misc programs

DisabledManual
exceptions06

use exceptions >=0.6

EnabledAutomatic
time15

use time >=1.5.0

EnabledAutomatic
transformers051

use transformers >=0.5.1

EnabledAutomatic
usehaskeline

use haskeline package

EnabledManual

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


Readme for toysolver-0.4.0

[back to package description]

toysolver

Join the chat at <a href="https://gitter.im/msakai/toysolver">https://gitter.im/msakai/toysolver</a>

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 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]

lpconvert

Converter between LP/MIP/SAT-related formats

Usage:

lpconvert -o [outputfile] [inputfile]

Supported formats:

  • Input formats: lp, mps, cnf, wcnf, opb, wbo
  • Output formats: lp, .mps, smt2, ys

pbconvert

Converter between SAT/PB-related formats

Usage:

pbconvert -o [outputfile] [inputfile]

Supported formats:

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

Bindings

TODO

  • Local search
  • Survey propagation