Optimization apparatus, optimization program, and optimization method

An optimization method of obtaining an approximate solution by performing optimization computation with respect to an optimization problem that involves a plurality of variables each taking either a first value or a second value, the plurality of variables grouped into a plurality of groups, among which any given group is under a constraint that an exactly predetermined number of variables among variables belonging to the given group take the second value, the optimization method comprising:

• performing optimization computation with respect to first variables subjected to optimization computation among variables belonging to one or more selected groups selected from the plurality of groups so as to obtain an approximate solution satisfying the constraint;
• and
• estimating and removing, based on the approximate solution, variables that are unlikely to take the second value in an optimal solution, thereby leaving second variables to remain in each of the one or more selected groups,
• wherein optimization computation is newly performed after updating the first variables with the second variables and third variables belonging to at least one unselected group, thereby repeatedly performing optimization computation by newly including, for each optimization computation, variables belonging to one or more previously unselected groups.

A non-transitory recording medium having a program embodied therein for obtaining an approximate solution by performing optimization computation with respect to an optimization problem that involves a plurality of variables each taking either a first value or a second value, the plurality of variables grouped into a plurality of groups, among which any given group is under a constraint that an exactly predetermined number of variables among variables belonging to the given group take the second value, the program causing a computer to perform:

• performing optimization computation with respect to first variables subjected to optimization computation among variables belonging to one or more selected groups selected from the plurality of groups so as to obtain an approximate solution satisfying the constraint;
• and
• estimating and removing, based on the approximate solution, variables that are unlikely to take the second value in an optimal solution, thereby leaving second variables to remain in each of the one or more selected groups,
• wherein optimization computation is newly performed after updating the first variables with the second variables and third variables belonging to at least one unselected group, thereby repeatedly performing optimization computation by newly including, for each optimization computation, variables belonging to one or more previously unselected groups.