An optimal solution search method for searching for an optimal solution in a combinatorial optimization problem using a computer, includes: acquiring a first solution candidate; and enumerating and indexing solution candidate groups of which the degree of divergence from the first solution candidate is equal to or smaller than a predetermined range; equally extracting second solution candidates from the enumerated and indexed solution candidate groups assigning evaluation values to the second solution candidates; and determining whether the search for the optimal solution is terminated on the basis of the evaluation value. In a case where the search for the optimal solution is not terminated, the current first solution candidate is updated as the best second solution candidate selected from the second solution candidates, and the processes are repeated until the search for the first optimal solution is terminated.