Pseudo-Boolean problems and their applications in engineering

OData support
Supervisor:
Dr. Mann Zoltán Ádám
Department of Computer Science and Information Theory

In my thesis I was involved with the different types of Pseudo-Boolean Problems, their solution techniques and application fields.

Pseudo-Boolean problems are special cases of Integer Linear Programming (ILP), in which every variable is expected to be 0 or 1. At the same time, Pseudo-Boolean Problems involve the Boolean nature of SAT (Boolean Satisfiability Problem) problems, and thus can be regarded as a combination of ILP and SAT problems.

Contrary to the past of ILP and SAT solvers that dates back more than a half century, the intensive development of Pseudo-Boolean solvers started a few years ago. The development was facilitated by the fact that former methods designed for ILP and SAT solvers are easily usable in Pseudo-Boolean solving algorithms. The benefit of Pseudo-Boolean solvers is that they are able to approach the performance of SAT solvers and the modeling capabilities of ILPs. Thus, Pseudo-Boolean solvers expected to be applicable in engineering fields.

In the first part of my thesis, I describe the solution methods of both the decision and the optimization versions of Pseudo-Boolean Problems, I review the different SAT- and ILP-based solution techniques and accelerating heuristics.

In the second part of my thesis, I exemplify the applicability of Pseudo-Boolean problems through two practical problems. With the help of the engineering applications and graph coloring benchmarks I performed empirical measurements. Therefore, I integrated Pseudo-Boolean and ILP solvers in the BCAT framework that helped to compare the efficiency of different Pseudo-Boolean and ILP techniques in the fields of hardware/software partitioning, frequency assignment and graph coloring.

Downloads

Please sign in to download the files of this thesis.