An optimization apparatus includes a storage unit that holds a weight coefficient representing the magnitude of an interaction between a plurality of state variables included in a first evaluation function representing a combinatorial optimization problem; a local solution computing unit that computes a local solution for the combinatorial optimization problem based on the first evaluation function; a selecting unit that selects a state variable group targeted by partial problems from the plurality of state variables based on a first state variable whose value at the local solution is a predetermined value among the plurality of state variables, the weight coefficient, and input selection region information; a searching unit that searches a ground state for a second evaluation function representing the partial problems for the selected state variable group; and a whole solution generating unit that generates a whole solution by updating the local solution based on the partial solutions acquired by the ground state search.