A statistical experiment to test practical convergence in one submodular programming problem

The article discusses a statistical experiment to test practical convergence in a single submodular programming problem. It proposes setting the problem of maximizing the sum of the group assignment effectiveness. The paper introduces the concept of a mixed solution of the transport task of group assignment, when resource constraints are met on average. It is shown that defining mixed solutions to the group assignment transport problem can be reduced to a submodular programming problem, which can be solved by the branch-and-bound method with upper estimates based on the transport problem submodularity with constraints in the form of column equalities. The polynomial nature of the ε-optimal version of the branch-and-bound method has been proved only in relation to the classical scheme for solving the multidi-mensional knapsack problem. We use a scheme that uses the specifics of the problem, therefore, further efforts are needed to test the polynomial hypothesis, including with the help of statistical experiments. The main result of the work is the development of a numerical implementation of the ε-optimal version of the branch-and-bound method in the high-level C++ programming language and conducting a statistical experiment to verify the practical convergence of the algorithm itself based on the statistical transport problem of group assignment by the effectiveness of the assignment. Based on the results of the numerical experiment analysis, it was found that for the problem under consideration, the percentage of vertices revealed during the operation of the ε-optimal algorithm from the total number of vertices in the orgraph decreases quite quickly with increasing dimensionality, which indicates sufficient efficiency of the algorithm. The polynomial hypothesis has not been confirmed, since the authors did not use a classical algorithm for solving an integer problem, but the specifics of the task.