D-FLAT System
A free software framework for rapid development of ASP-encoded dynamic programming algorithms that are based on tree decompositions. D-FLAT is developed within the project "Extending the Answer-Set Programming Paradigm to Decomposed Problem Solving".
Contents
About
D-FLAT (Dynamic Programming Framework with Local Execution of ASP on Tree Decompositions) is a tool that allows specification of dynamic programming algorithms operating on tree decompositions of a problem's (hyper)graph representation. This specification is done by means of logic programming under the answer set semantics. D-FLAT relieves the user from handling all the technical details concerned with parsing, tree decomposition, the handling of data structures, etc. Instead, it is only the dynamic programming algorithm itself which has to be specified in the ASP language. D-FLAT employs an ASP solver in order to compute the local solutions in the dynamic programming algorithm. It can therefore be used as a rapid prototyping tool for quickly implementing dynamic programming algorithms on tree decompositions.
TopPractice
D-FLAT provides a command line interface with options to specify the file containing the dynamic programming algorithm,
heuristics used for obtaining the tree decomposition of the input instance, and various output options, among others. For details,
invoke D-FLAT with option -h, or have a look at the documentation.
Running a simple 3-Col algorithm specified in the file 3col.lp, with the input graph in a file instance.lp and edges specified with the predicate edge/2, amounts to this call:
dflat -p 3col.lp -e edge < instance.lp
Example encodings
- Maximum Independent Set: use of table mode.
- Minimum Vertex Cover: use of table mode and lazy evaluation.
- Minimum Weighted Dominating Set: use of table mode, default join and counter incrementation.
- Secure Set: 2-layered, use of default join and built-in counters.
Download
We provide different versions of D-FLAT as well as a collection of example D-FLAT encodings and input instances for download.
The current development version of D-FLAT can be found in the D-FLAT repository on Github.
Among the example encodings, we provide implementations of different semantics for argumentation frameworks (see, e.g., Argumentation Project). The monolithic encodings for the argumentation problems are taken from the ASPARTIX Project.
Version 1.2.5
- New feature: Lazy evaluation now supports built-in counter arithmetic.
- Source code (published under the GPL), available at GitHub.
- Binaries: 32-bit, 64-bit.
- Documentation (DBAI Technical Report DBAI-TR-2017-107).
- Encodings collection.
All Versions
Example Instances
We provide a real world collection of traffic network instances, a downloader for instances which are in GTFS format, and a collection of instances of small treewidth for various problems, which was used for preliminary experiments.
TopTeam
People involved in the development of D-FLAT:
In case of questions, bug reports or comments, please send an e-mail to 
.