An optimization apparatus includes a compression unit, a storage unit, a decoding unit, and an annealing unit. The compression unit outputs compressed coefficient data in which a coefficient matrix including coupling coefficients, each of which indicates a coupling strength between bits of an Ising model obtained by converting a calculation target problem, is compressed on the basis of a symmetry property or a pattern property of the coefficient matrix. The storage unit holds the compressed coefficient data outputted by the compression unit. The decoding unit decodes the compressed coefficient data stored in the storage unit to obtain the coupling coefficients. The annealing unit performs a simulated annealing operation by using the coupling coefficients obtained by the decoding unit.