A BRANCH-AND-BOUND ALGORITHM FOR A PSEUDO-BOOLEAN OPTIMIZATION PROBLEM WITH BLACK-BOX FUNCTIONS

摘要

We consider a conditional pseudo-Boolean optimization problem with both the objective function and all constraint functions given algorithmically (black-box functions) and defined on {0, 1}n only. We suppose that these functions have certain properties, for example, unimodality and monotonicity. To solve problems of this type, we propose an optimization algorithm based on finding boundary points of the feasible region and the branch-and-bound method. The developed algorithm is aimed at the reception of an exact solution of an optimization problem. In addition, this algorithm can be used as an improvement of approximate algorithms such as the greedy heuristic and the random search algorithms for finding boundary points. Even after a small number of iterations (branchings), a significant improvement of the found feasible solution is achieved.