Controlled Random Search and Likelihood Ratio in Boolean Programming Problems

Based on the sequential probability ratio test (likelihood ratio) method, a controlled random search algorithm is proposed for the approximate solution of large-scale discrete programming problems. The reduction in the exhaustive search of feasible sets of the decision variables of the problem is achieved by introducing non-zero probabilities of false recognition of the optimal solution. As a practical application of the algorithm, the problem of forming optimal well placement patterns in oil and gas reservoirs is considered. The results of computational experiments are presented, the purpose of which was to study the accuracy of the problem’s solution depending on its dimension (the number of blocks where well placement is possible and the number of wells to be placed were varied). The optimal solution of the problem obtained by one of the exact methods of discrete programming was used as a reference solution, against which the accuracy of the approximate solution generated by the proposed algorithm was evaluated.