# Design of an environment for solving pseudo-Boolean optimization problems Bachelor’s thesis

Boolean Satisfiability problems (SAT) consists of finding a valid assignment (model) for a set of Boolean variables. It was the first problem proven to be NP-Complete which allowed reducing many NP-Complete problems to it. Because of this, it is one of the pillars of Computer Science.

An extension to SAT is Pseud-Boolean optimization problems. Unlike SAT, which can only express binary relationships among variables, Pseudo-Boolean optimization can formalize more complex relationships. These problems are defined in the following manner: Pseudo-Boolean Optimization formulation. Figure source: MPBO A Distributed Pseudo-Boolean Optimization Solver 

# Example: Knapsack problem

The variables for this problem, given $n$ objects, are: $$o_1, o_2, \ldots , o_n \text{for the objects}$$ $$w_1, w_2, \ldots , w_n \text{for the weights}$$ $$v_1, v_2, \ldots , v_n \text{for the values}$$ There is only one constraint which represent the maximum capacity of the knapsack problem: $$w_0 o_0 + w_1 o_1+ \ldots w_n o_n \leq knapsack’s \ capacity$$ And the cost function: $$v_0 o_0 + v_1 o_1+ \ldots v_n o_n$$