Algorithms for solving pseudo-Boolean optimization problems
We investigate the Pseudo-Boolean Optimization (PBO) problem, the Quadratic Unconstrained Binary Optimization (QUBO) problem, and the Boolean Quadratic Programming problem with Generalized Upper Bound constraints (BQP-GUB). These problems belong to the NP-hard computational class of problems and has been studied since the 1960s. The search for methods for solving these problems constitutes an active research field due to their applicability to model real-world situations. Encouraged by practical and theoretical demands, researchers have shown interest in developing methods for solving these problems. To effectively contribute to this field, we: (a) developed an exact algorithm for solving the PBO and QUBO problems; (b) designed a polynomial-time algorithm for solving specific classes of instances of the PBO and QUBO problems; (c) developed a formula for generating bounds on the optimal solution values for the QUBO problem instances; (d) created formulae for evaluating flip-moves that simultaneously change the values of several components of a solution vector for the BQP-GUB; and (e) reformulated combinatorial optimization problems to the form of QUBO and BQP-GUB.