An optimization device comprising: a plurality of annealing units (1a0,..., 1an) that performs a search process including, with respect to a change in a value of any of a plurality of state variables included in an evaluation function representing an energy, based on a change in the energy accompanying a change in a value of each of the plurality of state variables and a temperature, probabilistically determining which change of value of the plurality of state variables is accepted, and determining a value of each of the plurality of state variables with respect to the temperature; and an exchange control unit that retains correspondence information in which a plurality of pieces of identification information that identifies the plurality of annealing units is arranged in ascending or descending order of the temperature assigned to each of the plurality of annealing units, determines a plurality of first pairs of two annealing units having two adjacent temperatures based on the correspondence information, causes start of the search process by each of the annealing units associated with the temperature in the order of the temperature, performs a pipeline process including determining whether or not to perform, when the search processes by one first pair of the plurality of first pairs corresponding to the two temperatures are completed, exchange of the temperatures assigned to the one first pair without waiting for completion of the search processes by one or more first pairs other than the one first pair and exchanging the two temperatures of the two annealing units of the one first pair, updates the correspondence information when performing the exchange, and supplies temperature information representing the temperatures to the two annealing units based on the correspondence information after the update. a plurality of annealing units (1a0,..., 1an) that performs a search process including, with respect to a change in a value of any of a plurality of state variables included in an evaluation function representing an energy, based on a change in the energy accompanying a change in a value of each of the plurality of state variables and a temperature, probabilistically determining which change of value of the plurality of state variables is accepted, and determining a value of each of the plurality of state variables with respect to the temperature; and an exchange control unit that retains correspondence information in which a plurality of pieces of identification information that identifies the plurality of annealing units is arranged in ascending or descending order of the temperature assigned to each of the plurality of annealing units, determines a plurality of first pairs of two annealing units having two adjacent temperatures based on the correspondence information, causes start of the search process by each of the annealing units associated with the temperature in the order of the temperature, performs a pipeline process including determining whether or not to perform, when the search processes by one first pair of the plurality of first pairs corresponding to the two temperatures are completed, exchange of the temperatures assigned to the one first pair without waiting for completion of the search processes by one or more first pairs other than the one first pair and exchanging the two temperatures of the two annealing units of the one first pair, updates the correspondence information when performing the exchange, and supplies temperature information representing the temperatures to the two annealing units based on the correspondence information after the update.