An optimality degree computation unit computes an optimality degree in the case where a first variable included in a variable set is a candidate for an addition variable, using an objective function. An addition threshold computation unit computes an addition threshold based on the computed optimality degree, the addition threshold being a threshold of the optimality degree and indicating a criterion for determining whether or not the first variable is to be set as the candidate for the addition variable. An objective function value computation unit computes an objective function value which is a difference between a value of the objective function computed using variables to be optimized and a value of the objective function computed using the variables to be optimized from which a second variable included in a nonzero variable set is excluded.