Browsing by Author "Warro, Olli"
Now showing items 11 of 1

Warro, Olli (2023)In many realworld problems, the task is to find an optimal solution within a finite set of solutions. Many of the problems, also known as combinatorial optimization problems, are NPhard. In other words, finding an optimal solution for the problems is computationally difficult. However, being important for many realworld applications, there is a demand for efficient ways to solve the problems. One approach is the declarative approach, where the problems are first encoded into a mathematical constraint language. Then, the encoded problem instance is solved by an algorithm developed for that constraint language. In this thesis, we focus on declarative pseudoBoolean optimization (PBO). PBO is the set of integer programs (IP) where the variables can only be assigned to 0 or 1. For many realworld applications, finding an optimal solution is too timeconsuming. Instead of finding an optimal solution, incomplete methods attempt to find good enough solutions in a given time limit. To the best of our knowledge, there are not many incomplete algorithms developed specifically for PBO. In this thesis, we adapt an incomplete method developed for the maximum satisfiability problem to PBO. In the adapted algorithm, which we call LSORACLEPBO, a given PBO instance is solved using a form of local search that utilizes a pseudoBoolean decision oracle when moving from one solution to another. We implement and empirically compare LSORACLEPBO to another recent incomplete PBO algorithm called LSPBO. The results show that, in general, our implementation is not competitive against LSPBO. However, for some problem instances, our implementation provides better results than LSPBO.
Now showing items 11 of 1