A combination optimization apparatus includes: a storage unit that stores values of a plurality of state variables included in a first energy function given with a term representing a constraint condition for the plurality of state variables; and a processing unit that performs a search for the values of the plurality of state variables which minimize a value of the first energy function, wherein the search performed by the processing unit includes a first search performed by using the first energy function, a second search performed by using a second energy function obtained by removing the term representing the constraint condition from the first energy function after the first search, and a third search performed by using the first energy function after the second search.
展开▼