A problem solving operation apparatus obtains an optimum solution for a given problem through a combined use of a plurality of optimum solution search techniques of a genetic algorithm, and other search techniques like a hill climbing method. A combination of the optimum solution search techniques applied to each of a group of solution candidates varies according to each state. When a search efficiency in a single state is lowered, the problem solving operation apparatus immediately causes a state transition to the next state, thus enabling a search of an optimum solution through the use of another combination of more efficient optimum solution search techniques. Because a state transition constantly maintains a high search efficiency, this problem solving operation apparatus can reach an optimum solution in a short amount of time.