An optimization device of searching for an optimal solution of an optimization problem having a 2-Way 1-hot constraint, the optimization device comprising: a calculation circuit configured to calculate, for each of a plurality of first state variables, a first change amount of energy of an Ising model representing the optimization problem, the first change amount being a change amount caused by changing values of four state variables being selected based on the 2-Way 1-hot constraint from among a plurality of state variables in the Ising model, each of a plurality of first state variables being a state variable having a value of 0 among the plurality of state variables in the Ising model before the changing, the calculation circuit being configured to perform the calculating of the first change amount so as to satisfy the 2-Way 1-hot constraint that a sum of values of state variables included in each row is 1, and a sum of values of state variables included in each column is 1, when N (N is an integer of 2 or larger) squared state variables included in an evaluation function representing the energy of the Ising model are arrayed in N rows and N columns; a transition selection unit configured to select the four state variables allowed to change on the basis of the first change amount calculated for each of the plurality of first state variables, and output identification information for identifying the selected four state variables; an update circuit configured to update values of the four state variables allowed to change on the basis of identification information; a storage unit configured to store a plurality of weighting coefficients each indicating a magnitude of interaction between each two of the N squared state variables; and an address decoder configured to specify an address of the storage unit that stores a weighting coefficient group to be used for calculating the first change amount, of the plurality of weighting coefficients, on the basis of the identification information, wherein the storage unit is configured to read the weighting coefficient group at once on the basis of the address. a calculation circuit configured to calculate, for each of a plurality of first state variables, a first change amount of energy of an Ising model representing the optimization problem, the first change amount being a change amount caused by changing values of four state variables being selected based on the 2-Way 1-hot constraint from among a plurality of state variables in the Ising model, each of a plurality of first state variables being a state variable having a value of 0 among the plurality of state variables in the Ising model before the changing, the calculation circuit being configured to perform the calculating of the first change amount so as to satisfy the 2-Way 1-hot constraint that a sum of values of state variables included in each row is 1, and a sum of values of state variables included in each column is 1, when N (N is an integer of 2 or larger) squared state variables included in an evaluation function representing the energy of the Ising model are arrayed in N rows and N columns; a transition selection unit configured to select the four state variables allowed to change on the basis of the first change amount calculated for each of the plurality of first state variables, and output identification information for identifying the selected four state variables; an update circuit configured to update values of the four state variables allowed to change on the basis of identification information; a storage unit configured to store a plurality of weighting coefficients each indicating a magnitude of interaction between each two of the N squared state variables; and an address decoder configured to specify an address of the storage unit that stores a weighting coefficient group to be used for calculating the first change amount, of the plurality of weighting coefficients, on the basis of the identification information, wherein the storage unit is configured to read the weighting coefficient group at once on the basis of the address.