An optimization apparatus comprising: a searching unit configured to execute a search for a ground state of energy in an Ising model by using a plurality of temperature values and output a plurality of solutions; and a temperature setting unit configured to: select a first solution and a second solution from the plurality of solutions output from the searching unit, sequentially perform processing of calculating a change of the energy in the Ising model caused when one value of a plurality of bits of a bit sequence of the first solution different from bits of a bit sequence of the second solution is changed on each of the plurality of bits, compute, when an increase of the energy continuously occurs a plurality of number of times, a total value of the energies increased in the plurality of number of times, decide a maximum value of the plurality of temperature values based on the total value, and set the decided maximum value Z as a new maximum temperature value in the plurality of temperature values for the searching unit, wherein the searching unit is configured to repeat the search for the ground state by using the plurality of temperature values comprising the new maximum temperature value. a searching unit configured to execute a search for a ground state of energy in an Ising model by using a plurality of temperature values and output a plurality of solutions; and a temperature setting unit configured to: select a first solution and a second solution from the plurality of solutions output from the searching unit, sequentially perform processing of calculating a change of the energy in the Ising model caused when one value of a plurality of bits of a bit sequence of the first solution different from bits of a bit sequence of the second solution is changed on each of the plurality of bits, compute, when an increase of the energy continuously occurs a plurality of number of times, a total value of the energies increased in the plurality of number of times, decide a maximum value of the plurality of temperature values based on the total value, and set the decided maximum value Z as a new maximum temperature value in the plurality of temperature values for the searching unit, wherein the searching unit is configured to repeat the search for the ground state by using the plurality of temperature values comprising the new maximum temperature value. select a first solution and a second solution from the plurality of solutions output from the searching unit, sequentially perform processing of calculating a change of the energy in the Ising model caused when one value of a plurality of bits of a bit sequence of the first solution different from bits of a bit sequence of the second solution is changed on each of the plurality of bits, compute, when an increase of the energy continuously occurs a plurality of number of times, a total value of the energies increased in the plurality of number of times, decide a maximum value of the plurality of temperature values based on the total value, and set the decided maximum value Z as a new maximum temperature value in the plurality of temperature values for the searching unit, wherein the searching unit is configured to repeat the search for the ground state by using the plurality of temperature values comprising the new maximum temperature value.