An optimization device includes: a memory; and a processor and configured to: store a coefficient indicating magnitude of an interaction between bits in a bit string representing a state of an Ising model; output, when any bit in the bit string is inverted, a signal indicating inversion availability of an own bit according to calculation of energy change in the Ising model using the coefficient corresponding to the inverted bit and the own bit read from the memory as bit operations; output a signal indicating a bit to be inverted in the bit string selected on the basis of the signal indicating inversion availability output from bit operations of a first number of bits of the bit string, of the bit operations; and change the first number of bits and change a second number of bits of the coefficient for each bit operations of the first number of bits.