Optimal solution determination method, optimal solution determination program, and optimal solution determination device

Abstract

Provided is an optimal solution determination method for determining optimality of a solution in a combinatorial optimization problem using a computer, including uniformly extracting a plurality of solutions in a solution space of the combinatorial optimization problem as a plurality of first solutions, and estimating a maximum evaluation value in a case where solutions of a number that exceeds the number of the plurality of first solutions are assumed, on the basis of a plurality of first evaluation values respectively corresponding to the plurality of first solutions that are uniformly extracted, as a first maximum evaluation value Z. Further, in a case where a solution candidate (graph G_1) that belongs to a solution space is input (step S), an evaluation value S_1 corresponding to the graph G_1 is acquired, the acquired evaluation value S_1 is compared with the first maximum evaluation value Z, and it is determined whether the evaluation value S_1 of the input graph G_1 is within a confidence interval of the first maximum evaluation value Z (whether the graph G_1 is a first optimal value or not).