Back to first pageBack to first page Centre for Artificial Intelligence of UNL
Browse our site
You are here:

Publication details

Go back
Publication details
Main information
Towards Solving a System of Pseudo Boolean
October 2008
Eich08
In this work we address the applicability of binary decision diagrams (BDDs) for solving combinatorial (NP complete) problems. Typically, these problems are represented in conjunctive normal form (CNF), but we analyze problems specified as a conjunction of pseudo Boolean constraints (PBC), which is a more compact representation. We present a recently published algorithm that transforms a PBC into a BDD, and provide a different correctness proof. After this initial transformation all PBCs are encoded as BDDs. Then we consider two approaches to compute a solution to the complete problem. The main work of this thesis lies in the analysis on how propagation is possible with BDDs. We present different techniques and conclude by proposing a propagation directed BDD data structure, UPBDDs. Although not being able to compete in general with current solvers, we show with a selection of benchmark problems the potential of the monolithic and search based method.
In proceedings
Valentin Mayer-Eichberger
M.Sc. Thesis
-
-
-
-
-
-
-
-
http://centria.di.fct.unl.pt/~pb/papers/ValentinThesis.pdf
Export formats
Valentin Mayer-Eichberger, Towards Solving a System of Pseudo Boolean, , M.Sc. Thesis, (http://centria.di.fct.unl.pt/~pb/papers/ValentinThesis.pdf), October 2008.
Valentin Mayer-Eichberger, <b>Towards Solving a System of Pseudo Boolean</b>, <u>M.Sc. Thesis</u>, (<a href="http://centria.di.fct.unl.pt/~pb/papers/ValentinThesis.pdf" target="_blank">url</a>), October 2008.
@inproceedings {Eich08, author = {Valentin Mayer-Eichberger}, title = {Towards Solving a System of Pseudo Boolean}, booktitle = {M.Sc. Thesis}, url = {http://centria.di.fct.unl.pt/~pb/papers/ValentinThesis.pdf}, abstract = {In this work we address the applicability of binary decision diagrams (BDDs) for solving combinatorial (NP complete) problems. Typically, these problems are represented in conjunctive normal form (CNF), but we analyze problems specified as a conjunction of pseudo Boolean constraints (PBC), which is a more compact representation. We present a recently published algorithm that transforms a PBC into a BDD, and provide a different correctness proof. After this initial transformation all PBCs are encoded as BDDs. Then we consider two approaches to compute a solution to the complete problem. The main work of this thesis lies in the analysis on how propagation is possible with BDDs. We present different techniques and conclude by proposing a propagation directed BDD data structure, UPBDDs. Although not being able to compete in general with current solvers, we show with a selection of benchmark problems the potential of the monolithic and search based method.}, month = {October}, year = {2008}, }
Publication's urls
/publications/view.php?code=df7a98824e45a9e9a830f2d2eb2adeff
/publications/view.php?code=Eich08
Go back
Centre for Artificial Intelligence of UNL
Departamento de Informática, FCT/UNL
Quinta da Torre 2829-516 CAPARICA - Portugal
Tel. (+351) 21 294 8536 FAX (+351) 21 294 8541

Fundacao_FCT