A propositional CONEstrip algorithm
- Author
- Erik Quaeghebeur (UGent)
- Organization
- Abstract
- 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.
- Keywords
- OPTIMIZATION, PROBABILITY, LOGIC, sets of desirable gambles, linear programming, row generation, satisfiability, SAT, PSAT, WPMaxSAT, consistency, coherence, inference, natural extension
Downloads
-
Quaeghebeur-IPMU14p.pdf
- full text
- |
- open access
- |
- |
- 368.75 KB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU-5814652
- MLA
- Quaeghebeur, Erik. “A Propositional CONEstrip Algorithm.” Communications in Computer and Information Science, edited by Anne Laurent et al., vol. 444, Springer, 2014, pp. 466–75, doi:10.1007/978-3-319-08852-5_48.
- APA
- Quaeghebeur, E. (2014). A propositional CONEstrip algorithm. In A. Laurent, O. Strauss, B. Bouchon-Meunier, & R. R. Yager (Eds.), Communications in Computer and Information Science (Vol. 444, pp. 466–475). https://doi.org/10.1007/978-3-319-08852-5_48
- Chicago author-date
- Quaeghebeur, Erik. 2014. “A Propositional CONEstrip Algorithm.” In Communications in Computer and Information Science, edited by Anne Laurent, Olivier Strauss, Bernadette Bouchon-Meunier, and Ronald R Yager, 444:466–75. Springer. https://doi.org/10.1007/978-3-319-08852-5_48.
- Chicago author-date (all authors)
- Quaeghebeur, Erik. 2014. “A Propositional CONEstrip Algorithm.” In Communications in Computer and Information Science, ed by. Anne Laurent, Olivier Strauss, Bernadette Bouchon-Meunier, and Ronald R Yager, 444:466–475. Springer. doi:10.1007/978-3-319-08852-5_48.
- Vancouver
- 1.Quaeghebeur E. A propositional CONEstrip algorithm. In: Laurent A, Strauss O, Bouchon-Meunier B, Yager RR, editors. Communications in Computer and Information Science. Springer; 2014. p. 466–75.
- IEEE
- [1]E. Quaeghebeur, “A propositional CONEstrip algorithm,” in Communications in Computer and Information Science, Montpellier, france, 2014, vol. 444, pp. 466–475.
@inproceedings{5814652,
abstract = {{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.}},
author = {{Quaeghebeur, Erik}},
booktitle = {{Communications in Computer and Information Science}},
editor = {{Laurent, Anne and Strauss, Olivier and Bouchon-Meunier, Bernadette and Yager, Ronald R}},
isbn = {{9783319088525}},
issn = {{1865-0929}},
keywords = {{OPTIMIZATION,PROBABILITY,LOGIC,sets of desirable gambles,linear programming,row generation,satisfiability,SAT,PSAT,WPMaxSAT,consistency,coherence,inference,natural extension}},
language = {{eng}},
location = {{Montpellier, france}},
pages = {{466--475}},
publisher = {{Springer}},
title = {{A propositional CONEstrip algorithm}},
url = {{http://doi.org/10.1007/978-3-319-08852-5_48}},
volume = {{444}},
year = {{2014}},
}
- Altmetric
- View in Altmetric
- Web of Science
- Times cited: