Technique for solving optimization problem

A method comprising:

• causing, by a computer, a cylindrical algebraic decomposition processing unit that carries out a projection processing to carry out the projection processing for a first expression that appears in a quantifier elimination problem equivalent to an optimization problem including a plurality of objective functions and to generate second expressions that are projection factors of the first expression;
• obtaining, by the computer, data of the generated second expressions from the cylindrical algebraic decomposition processing unit;
• first calculating, by the computer, a plurality of sets of values of the plurality of objective functions by generating a plurality of value sets of variables in the plurality of objective functions and substituting the generated plurality of value sets of the variables into the plurality of objective functions;
• extracting, by the computer, points including non-dominated solutions in a space mapped by values of the plurality of objective functions, from a plurality of points corresponding to the plurality of sets of values;
• second calculating, by the computer, for each of the second expressions, an evaluation value concerning a distance between a corresponding second expression and each of the extracted points;
• and
• identifying, by the computer, a second expression whose evaluation value is minimum.

An apparatus comprising:

• a storage device;
• a controlling unit that causes a cylindrical algebraic decomposition processing unit that carries out a projection processing to carry out the projection processing for a first expression that appears in a quantifier elimination problem equivalent to an optimization problem including a plurality of objective functions and to generate second expressions that are projection factors of the first expression and obtains data of the generated second expressions from the cylindrical algebraic decomposition processing unit;
• a generating unit that calculates a plurality of sets of values of the plurality of objective functions by generating a plurality of value sets of variables in the plurality of objective functions and substituting the generated plurality of value sets of the variables into the plurality of objective functions, and extracts points including non-dominated solutions in a space mapped by values of the plurality of objective functions, from a plurality of points corresponding to the plurality of sets of values;
• and
• a selecting unit that calculates, for each of the second expressions, an evaluation value concerning a distance between a corresponding second expression and each of the extracted points, stores the evaluation value into the storage device in association with the second expression, and identifies a second expression whose evaluation value is minimum.

An apparatus comprising:

• a processor configured to execute a procedure, the procedure comprising:
• causing a cylindrical algebraic decomposition processing unit that carries out a projection processing to carry out the projection processing for a first expression that appears in a quantifier elimination problem equivalent to an optimization problem including a plurality of objective functions and to generate second expressions that are projection factors of the first expression;
• obtaining data of the generated second expressions from the cylindrical algebraic decomposition processing unit;
• first calculating a plurality of sets of values of the plurality of objective functions by generating a plurality of value sets of variables in the plurality of objective functions and substituting the generated plurality of value sets of the variables into the plurality of objective functions;
• extracting points including non-dominated solutions in a space mapped by values of the plurality of objective functions, from a plurality of points corresponding to the plurality of sets of values;
• second calculating for each of the second expressions, an evaluation value concerning a distance between a corresponding second expression and each of the extracted points;
• and
• identifying a second expression whose evaluation value is minimum.