Skip to main content

Qualitative and quantitative optimization in answer set programming

Project description

# asprin
> A general framework for qualitative and quantitative optimization in answer set programming.

## Description
`asprin` is a general framework for optimization in ASP that allows:
* computing optimal stable models of logic programs with preferences, and
* defining new preference types in a very easy way.
Some preference types (`subset`, `pareto`...) are already defined in `asprin`'s library,
but many more can be defined simply writing a logic program.

For a formal description of `asprin`, please read our [paper](http://www.cs.uni-potsdam.de/wv/pdfformat/brderosc15a.pdf) ([bibtex](http://www.cs.uni-potsdam.de/wv/bibtex/brderosc15a.bib)).

Starting with version 3, `asprin` is documented in the [Potassco guide](https://github.com/potassco/guide/releases/).
Older versions are documented in the [Potassco guide on Sourceforge](https://sourceforge.net/projects/potassco/files/guide/).


## Usage
```bash
$ asprin [number_of_models] [options] [files]
```
By default, `asprin` loads its library `asprin_lib.lp`. This may be disabled with option `--no-asprin-lib`.

Option `--help` prints help.

Options `--approximation=weak` and `--approximation=heuristic` activate solving modes different than the basic ones,
and are often faster than it.

Option `--meta=query` can be used to compute optimal models that contain the atom `query`.

Options `--meta=simple` or `--meta=combine` should be used to compute many optimal models using
non stratified preference programs (in `asprin`'s library this can only happen with CP nets, see below).

Option `--on-opt-heur` can be used to enumerate diverse (or similar) optimal stable models.
For example, try with `--on-opt-heur=+,p,1,false --on-opt-heur=-,p,1,true`.

Option `--improve-limit` can be used to enumerate close to optimal stable models.
For example, try with `--improve-limit 2,1000`.

## Building

<!--- TO BE CHANGED -->
The easiest way to obtain `asprin` is using Anaconda.
Packages are available in the Potassco channel.
First install either Anaconda or Miniconda and then run:
`conda install -c potassco asprin`.
<!--- -->

`asprin` can also be installed with [pip](https://pip.pypa.io) via
```pip install asprin```.
For a local installation, add option ```--user```.
In this case, setting environment variable `PYTHONUSERBASE` to `dir` before running `pip`,
`asprin` will be installed in `dir/bin/asprin`.

<!--- TO BE CHANGED -->
If that does not work,
you can always download the sources from
[here](https://github.com/potassco/asprin/releases/download/v3.1.0/asprin-3.1.0.tar.gz) in some directory `dir`,
and run `asprin` with `python dir/asprin/asprin/asprin.py`.
<!--- -->

System tests may be run with ```asprin --test``` and ```asprin --test --all```.

`asprin` has been tested with `Python 2.7.13` and `3.5.3`, using `clingo 5.3.0`.

```asprin``` uses the `ply` library, version `3.11`,
which is bundled in [asprin/src/spec_parser/ply](https://github.com/potassco/asprin/tree/master/asprin/src/spec_parser/ply),
and was retrieved from http://www.dabeaz.com/ply/.

## Examples
```
$ cat examples/example1.lp
dom(1..3).
1 { a(X) : dom(X) }.
#show a/1.

#preference(p,subset) {
a(X)
}.
#optimize(p).


$ asprin examples/example1.lp 0
asprin version 3.0.0
Reading from examples/example1.lp
Solving...
Answer: 1
a(3)
OPTIMUM FOUND
Answer: 2
a(2)
OPTIMUM FOUND
Answer: 3
a(1)
OPTIMUM FOUND

Models : 3
Optimum : yes
Optimal : 3

$ cat examples/example2.lp
%
% base program
%

dom(1..3).
1 { a(X) : dom(X) } 2.
1 { b(X) : dom(X) } 2.
#show a/1.
#show b/1.

%
% basic preference statements
%

#preference(p(1),subset){
a(X)
}.

#preference(p(2),less(weight)){
X :: b(X)
}.

#preference(p(3),aso){
a(X) >> not a(X) || b(X)
}.

#preference(p(4),poset){
a(X);
b(X);
a(X) >> b(X)
}.

%
% composite preference statements
%

#preference(q,pareto){
**p(X)
}.

#preference(r,neg){
**q
}.

%
% optimize statement
%

#optimize(r).

$ asprin examples/example2.lp
asprin version 3.0.0
Reading from examples/example2.lp
Solving...
Answer: 1
a(3) b(1)
OPTIMUM FOUND

Models : 1+
Optimum : yes
```

## CP nets

`asprin` preference library implements the preference type `cp`,
that stands for *CP nets*.

CP nets where introduced in the following paper:
* Craig Boutilier, Ronen I. Brafman, Carmel Domshlak, Holger H. Hoos, David Poole:
CP-nets: A Tool for Representing and Reasoning with Conditional Ceteris Paribus Preference Statements.
J. Artif. Intell. Res. 21: 135-191 (2004)

Propositional preference elements of type `cp` have one of the following forms:
1. `a >> not a || { l1; ...; ln }`, or
2. `not a >> a || { l1; ...; ln }`

where `a` is an atom and `l1`, ..., `ln` are literals.

The semantics is defined using the notion of improving flips.
Let `X` and `Y` be two interpretations of a logic program.
There is an improving flip from `X` to `Y` if
there is some preference element such that `X` and `Y` satisfy all `li`'s, and either
the element has the form (1) and `Y` is the union of `X` and `{a}`,
or
the element has the form (2) and `Y` is `X` minus `{a}`.
Then, `W` is better than `Z` if there is a sequence of improving flips from `W` to `Z`.
A CP net is consistent if there is no interpretation `X` such that `X` is better than `X`.


We provide various encoding and solving techniques for CP nets,
that can be applied depending on the structure of the CP net.
For tree-like CP nets, see example [cp_tree.lp](https://github.com/potassco/asprin/blob/master/asprin/examples/cp_tree.lp).
For acyclic CP nets, see example [cp_acyclic.lp](https://github.com/potassco/asprin/blob/master/asprin/examples/cp_acyclic.lp).
For general CP nets, see example [cp_general.lp](https://github.com/potassco/asprin/blob/master/asprin/examples/cp_general.lp).

`asprin` implementation of CP nets is correct only for consistent CP nets.
Note that tree-like and acyclic CP nets are always consistent, but this does not hold in general.


## Contributors

* Javier Romero


Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Filename, size & hash SHA256 hash help File type Python version Upload date
asprin-3.1.0-py2-none-any.whl (212.4 kB) Copy SHA256 hash SHA256 Wheel py2
asprin-3.1.0.tar.gz (143.1 kB) Copy SHA256 hash SHA256 Source None

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page