Bug#1063388: ITP: chuffed -- lazy clause generation CP solver
Package: wnpp
Severity: wishlist
Owner: Kari Pahula <kaol@debian.org>
X-Debbugs-Cc: debian-devel@lists.debian.org, debian-science@lists.debian.org
* Package name : chuffed
Version : 0.13.1
* URL : https://github.com/chuffed/chuffed
* License : MIT/X
Programming Lang: C++
Description : lazy clause generation CP solver
Chuffed is a state of the art lazy clause solver designed from the
ground up with lazy clause generation in mind. Lazy clause generation
is a hybrid approach to constraint solving that combines features of
finite domain propagation and Boolean satisfiability. It combines some
of the advantages of finite domain constraint programming (high level
model and programmable search) with some of the advantages of SAT
solvers (reduced search by nogood creation, and effective autonomous
search using variable activities).
Chuffed only supports 3 different propagator priorities. Chuffed
implements a number of global propagators (alldiff, inverse, minimum,
table, regular, mdd, cumulative, disjunctive, circuit, difference). It
also only supports two kinds of integer variables. Small integer
variables for which the domain is represented by a byte string. And
large integer variables for which the domain is represented only by
its upper and lower bound (no holes allowed). All boolean variables
and boolean constraints are handled by the builtin SAT solver.
The solver, when run with lazy clause generation disabled, is somewhat
comparable in speed with older versions of Gecode. The overhead from
lazy clause generation ranges from negligible to perhaps around
100%. The search reduction, however, can reach orders of magnitude on
appropriate problems. Thus lazy clause generation is an extremely
important and useful technology.
The easiest way to use Chuffed is as a backend to the MiniZinc
constraint modelling language. Chuffed can also be used as a C++
library.
The description is edited from upstream's description, it went into
more detail than this about the implementation. For certain types of
CP problems it works better than the alternatives.
Chuffed is both a library and it provides a binary (fzn-chuffed). The
library can be used as a dependency for both minizinc and minizinc-ide
(which I maintain) and it provides an alternative flatzinc
implementation for minizinc.
I plan to maintain this under the Debian Science team.
As of now upstream is building chuffed as a static library only but
I'll try to convince them to provide a shared library before packaging
it.
Reply to: