Optimization apparatus, optimization method, and non-transitory computer-readable storage medium

An optimization apparatus comprising:

• a temperature control circuit to control a temperature value indicating a temperature,
• annealing circuits configured to:
• calculate a change amount of energy represented by an evaluation function the evaluation function including a plurality of binary state variables and at least one multi-valued auxiliary spin which represents a range constraint for a sum related to the plurality of binary state variables, and
• a processor coupled to the temperature control circuit and the annealing circuits and configured to:
• determine whether to set a state change in any of the binary state variables or the multi-valued auxiliary spin as a candidate according to a correlation between a threshold and a total change amount, the threshold being calculated based on the temperature value and a random number value, the total change amount being obtained by the calculated change amount of energy, the state change for the multi-valued auxiliary spin comprises incrementing or decrementing its value by 1 to traverse a continuous integer range of the range constraint,
• stochastically determine whether to adopt the state change set as the candidate,
• calculate post-transition energy after executing a state transition of the state variable according to the state change, and
• obtain minimum energy by setting the post-transition energy as the minimum energy when the post-transition energy is less than the minimum energy.