Using interval techniques of direct comparison and differential formulation to solve a multi-objective optimization problem

A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a computer-controlled method for using interval techniques within a computer system to solve a multi-objective optimization problem and identify a solution set that represents an optimal trade-off solution, the method comprising:

• receiving a representation of multiple objective functions at the computer system;
• receiving a representation of a domain of interest for the multiple objective functions, wherein the domain of interest is an interval within which function variables for the objective functions lie;
• storing the representations in a memory within the computer system;
• and
• performing a composite interval optimization process in order to identify guaranteed bounds on a Pareto front for the multiple objective functions, wherein the composite process comprises a direct comparison technique and an interval version of a differential formulation,
• wherein performing the portion of the interval optimization process comprising the direct comparison technique involves:
• determining a first box covering the entire received domain of interest, and subdividing the first box into other boxes;
• maintaining influence information for the other boxes in the received domain of interest, wherein for a given box the influence information identifies other boxes which are in the range of influence of the given box and/or in the domain of influence of the given box, wherein the range and domain of influence of the given box describe the range and domain of possible dominance,
• using the influence information to identify boxes to be tested against each other for domination,
• testing boxes against each other to determine which boxes are certainly dominated by other boxes, and
• eliminating boxes which are certainly dominated by other boxes;
• and
• wherein performing the portion of the interval optimization process comprising the interval version of the differential formulation involves:
• applying a gradient technique to the remaining boxes to eliminate boxes that do not have a local Pareto optimum;
• and
• identifying the remaining boxes as representing guaranteed bounds on a Pareto front for the received representation of the multiple objective functions, wherein the guaranteed bounds are machine-representable upper and lower bounds on the Pareto front for the received representation of the multiple objective functions;
• identifying a solution set of optimal points on the Pareto front using the guaranteed bounds of the Pareto front, wherein for each point within the guaranteed bounds on the Pareto front, an improvement in one objective function cannot be made without adversely affecting at least one other objective function;
• and
• identifying values of the objective functions' independent variables that are mapped to the set of optimal points on the Pareto front.

An apparatus for using interval techniques within a computer system to solve a multi-objective optimization problem and identify a solution set that represents an optimal trade-off solution, comprising:

• a receiving mechanism configured to receive a representation of multiple objective functions at the computer system;
• wherein the receiving mechanism is additionally configured to receive a representation of a domain of interest for the multiple objective functions, wherein the domain of interest is an interval within which function variables for the objective functions lie;
• a storage mechanism configured to store the representations in a memory within the computer system;
• and
• an optimization mechanism configured to perform a composite-interval optimization process in order to identify guaranteed bounds on a Pareto front for the multiple objective functions, wherein the composite process comprises a direct comparison technique and an interval version of a differential formulation, wherein while performing the portion of the interval optimization process comprising the direct comparison technique, the optimization mechanism is configured to,
• determine a first box covering the entire received domain of interest, and subdivide the first box into other boxes;
• maintain influence information for the other boxes in the received domain of interest, wherein for a given box the influence information identifies other boxes which are in the range of influence of the given box and/or in the domain of influence of the given box, wherein the range and domain of influence of the given box describe the range and domain of possible dominance,
• use the influence information to identify boxes to be tested against each other for domination,
• test boxes against each other to determine which boxes are certainly dominated by other boxes, and
• eliminate boxes which are certainly dominated by other boxes;
• and
• wherein, while performing the portion of the interval optimization process comprising the interval version of the differential formulation, the optimization mechanism is further configured to:
• apply a gradient technique to the remaining boxes to eliminate boxes that do not have a local Pareto optimum;
• and
• identify the remaining boxes as representing guaranteed bounds on a Pareto front for the received representation of the multiple objective functions, wherein the guaranteed bounds are machine-representable upper and lower bounds on the Pareto front for the received representation of the multiple objective functions;
• identify a solution set of optimal points on the Pareto front using the guaranteed bounds of the Pareto front, wherein for each point within the guaranteed bounds on the Pareto front, an improvement in one objective function cannot be made without adversely affecting at least one other objective function;
• and to
• identify values of the objective functions' independent variables that are mapped to the set of optimal points on the Pareto front.