Skip to main content

An implementation of the CONEstrip algorithms using python and z3.

Project description

The CONEstrip library

This repository contains a Python framework for reasoning with uncertainty. This is joint work with Erik Quaeghebeur. N.B. This is ongoing work, so not everything is finished yet.

The CONEstrip algorithm

In the paper The CONEstrip algorithm (SMPS 2012), an algorithm is defined that determines whether a finitely generated general convex cone contains the origin.

Uncertainty models such as sets of desirable gambles and (conditional) lower previsions can be represented as convex cones. Checking the consistency of and drawing inferences from such models requires solving feasibility and optimization problems. We consider finitely generated such models. For closed cones, we can use linear programming; for conditional lower prevision-based cones, there is an efficient algorithm using an iteration of linear programs. We present an efficient algorithm for general cones that also uses an iteration of linear programs.

The Propositional CONEstrip algorithm

In the paper A propositional CONEstrip algorithm (IPMU 2014) a generalization of the CONEstrip algorithm is presented.

We present a variant of the CONEstrip algorithm for checking whether the origin lies in a finitely generated convex cone that can be open, closed, or neither. This variant is designed to deal efficiently with problems where the rays defining the cone are specified as linear combinations of propositional sentences. The variant differs from the original algorithm in that we apply row generation techniques. The generator problem is WPMaxSAT, an optimization variant of SAT; both can be solved with specialized solvers or integer linear programming techniques. We additionally show how optimization problems over the cone can be solved by using our propositional CONEstrip algorithm as a preprocessor. The algorithm is designed to support consistency and inference computations within the theory of sets of desirable gambles. We also make a link to similar computations in probabilistic logic, conditional probability assessments, and imprecise probability theory.

Implementation

In the CONEstrip algorithm several linear programming problems need to be solved. This has been implemented using Z3. Note that it is also possible to solve them with a library like cddlib.

The propositional CONEstrip algorithm is defined in terms of WPMaxSAT problems. We note that WPMaxSAT problems can be conveniently expressed using the propositional logic of Z3. Hence, also this algorithm has been implemented using Z3.

Documentation

A detailed specification of the implementation can be found in CONEstrip.pdf. Note that this is not a tutorial, but rather a precise description of the algorithms that were implemented.

Installation

The code is available as the PyPI package CONEstrip. It can be installed using

pip install CONEstrip

Licensing

The code is available under the Boost Software License 1.0. A local copy is included in the repository.

For testing the Toy Parser Generator package is used. This package is available under the GNU Lesser General Public License v2.1 license. A local copy is included in the repository.

Project details


Download files

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

Source Distribution

CONEstrip-0.1.1.tar.gz (25.1 kB view details)

Uploaded Source

Built Distribution

CONEstrip-0.1.1-py3-none-any.whl (28.1 kB view details)

Uploaded Python 3

File details

Details for the file CONEstrip-0.1.1.tar.gz.

File metadata

  • Download URL: CONEstrip-0.1.1.tar.gz
  • Upload date:
  • Size: 25.1 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.2 CPython/3.10.6

File hashes

Hashes for CONEstrip-0.1.1.tar.gz
Algorithm Hash digest
SHA256 ac57b04fd299cc298f1f090c7d5db35f5e5605805c0cafe2ef5ef3fa36b24562
MD5 876b6debe6146439c63a2e8bd4fac8f6
BLAKE2b-256 449afb7ac1305dfa0738dbc56527dadb4b5ef852bf15d716fded05daf1ec6672

See more details on using hashes here.

File details

Details for the file CONEstrip-0.1.1-py3-none-any.whl.

File metadata

  • Download URL: CONEstrip-0.1.1-py3-none-any.whl
  • Upload date:
  • Size: 28.1 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.2 CPython/3.10.6

File hashes

Hashes for CONEstrip-0.1.1-py3-none-any.whl
Algorithm Hash digest
SHA256 d99e1e12f01d9d438a7a5a0d55abe97d981decc09f6175d759c4111792ccad78
MD5 d04b5676676ad7be30e36969568b9742
BLAKE2b-256 87589e43806ad25da5623648151c473cc6c1c9d88bf1bd1f30a516945f548df1

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page