Method for solving multidimensional optimization problems The invention concerns a method for solving multidimensional optimization problems on a set of feasible solutions of a discrete combinatorial problem by means of a computer pro ^¬ gram . In many economical and technical domains, discrete combinato ^¬ rial problems play an important role for problem formulation and reasoning. Examples of such discrete combinatorial prob ^¬ lems are:

- The knowledge-based configuration of products and services as described in http://en.wikipedia.org/wiki/Knowledge- basecl_configuration;

- product line engineering, which has established itself as a standard practice for exploiting the commonalities among a family of products and managing the variabilities among them in a systematic way;

- recommender systems, which are used for predicting the rating a user would give to a certain product or piece of infor ^¬ mation;

- scheduling, that are methods by which threads, processes or data flows are given access to system resources, e.g. proces ^¬ sor time or communications bandwidth;

- decision support systems, that are computer-based informa ^¬ tion system that supports business or organizational deci ^¬ sion-making activities;

- "OR problems" as described in C. H. Papaclimitriou, K. Stei- glitz. Combinatorial Optimization : Algorithms and Complexity. Prentice-Hall, 1982; second edition, Dover, 1998.

In a general way, discrete combinatorial problems are defined as follows: Given are a problem domain description and a set of requirements for a concrete problem (e.g., both in form of a logical theory) . The task is to find one or all solutions to the concrete problem.

The solutions which obey the domain description and the re- quirements are called feasible solutions S = {Si, S _n } .

Searching for feasible solutions is often not enough, but the subset of feasible solutions which minimize or maximize sev ^¬ eral optimization criteria are of interest.

The tasks to find this solutions are known as multidimen- sional optimization problems.

Optimization criteria are represented as optimization func ^¬ tions

f± : S → R

computing a numeric optimization value for each solution. The set of best solutions S ^* c: S contains those solutions S which minimize or maximize all the optimization functions.

There are two major models how to deal with multiple optimi ^¬ zation criteria: Pareto optimality as described in

http://en.wikipedia.org/wiki/Pareto_efficiency and the weighted sum model.

The weighted sum model simply condenses all the optimization function to a single function by summing them up. Usually weight factors are involved to represent the importance of the different optimization criteria.

k

min^w, */,·(5' _ί ) , for solutions Si, k optimization criteria, and j=i

weights W for each criterion j

Examples of optimization criteria are:

• price (of unit Euro)

• maintenance costs (of unit h/year)

· CO2 footprint (of unit kg/year)

• power consumption (of unit W) We see that all these criteria are of different units, so, mathematically, it does not make any sense to directly sum them up. They have to be normalized to a common unit system. A normalization function is a projection from one range (unit system) to another (the common unit system) .

Known systems for representing and solving discrete combinatorial problems can cope only with a single optimization function. Examples of such systems are ILOG, CHOCO, or Answer Set Programming systems like Potassco DLV.

To use these systems for multidimensional optimization prob ^¬ lems, the multiple optimization functions must be accumulated to a single optimization function. The main approach is a weighted sum model .

In this approach, the crucial step is to normalize the dif ^¬ ferent optimization functions to a standard unit system. To define robust normalization functions is not a trivial task and is usually done in a heuristic way by analyzing the range of the optimization function and designing the normalization projection. E.g., the range of an optimization criterion "C02 footprint" (of unit kg/year) depends on the various parts in the component catalogue, the selection of parts for a solu ^¬ tion and the size of the solution. It is often difficult to find meaningful minimum and maximum values.

Often, the min-max model is used, where the minimum and maxi ^¬ mum optimization function value is computed or estimated. The projection function of the min-max normalization model is then :

fAS^ - min

norm (f (5,. )) =— _: —

max- min

The values of an optimization function are often not distrib ^¬ uted equally throughout all possible solutions, leading to deformations of the overall optimization value.

The disadvantages of such heuristic normalization functions are that they must be designed separately for each optimiza- tion criterion and each domain, they may lead to faulty cal ^¬ culations if not the whole range has been taken into account (e.g., if lower or higher values than the estimated min and max values show up) , and they may lead to deformations of the optimization functions if the value distribution of the raw data does not match the value distribution of the normalized data .

It is a goal of this invention to disclose a more robust, general and domain-independent model for normalization func- tions especially for the use in knowledged base

This is done with a method according to claim 1.

The new normalization method is completely domain- independent. It can be applied to every normally distributed optimization function in a general way. This will reduce mod ^¬ elling time and code complexity.

The new normalization method is based on standard sta ^¬ tistics methods and is very easy to understand and to com- pute.

Because of its general and domain-independent nature, the new normalization method is robust. E.g., during the modelling phase, when standard deviations of optimization func ^¬ tions are computed, standard outlier detection methods can easily be integrated to avoid distorted normalization func ^¬ tions. In contrast, heuristic normalization functions some ^¬ times must use artificial cut-offs for the projection func ^¬ tion which may lead to the same optimization values for dif ^¬ ferent raw values.

By having a simple and robust method for the definition of normalization functions, the application of multidimensional optimization is easier to implement. This gets more and more important in the future, where not only the price of a system (e.g. a configured product) is to be taken into account, but also other criteria like • sustainability : a higher rating of products which con ^¬ sist of sustainable parts and materials, and which contribute to a sustainable usage of valuable resources

green technology: higher rating of products which con- sist of regional resources (shorter routes of transport, pro ^¬ motion of local economy) , which are produced with less environmental pollution, which have a longer span of life, ...

• strategic preferences: higher rating of products which are, e.g., currently available in stock.

The method according to the invention is exemplified with an example shown in Fig. 1

Fig. 1 shows the calculation schema for accumulation of sev- eral optimization values to a single optimization value.

The task of normalizing optimization criteria with different units (e.g. price in Euro, C02 footprint in kg/year, mainte ^¬ nance costs in h/year) to a standard unit so that they can be accumulated to a single optimization value is usually done by heuristic, domain-dependent normalization functions.

According to the invention, standard deviation is used for normalization .

The process is described in the following:

Let be S the set of all feasible solutions to a discrete com ^¬ binatorial problem.

Let S _{s amp} i _e = { S i , ... , S _n } be a set of sample solutions. This set of sample solutions is a subset of all feasible solutions S . The sample solutions must be a representative set of solu- tions. An example of such a set of sample solutions is the set of products sold in the last time period.

Let {f i , f^ } be a set of optimization functions. An opti ^¬ mization function fi : S — is a function which computes a "raw" (i.e., un-normalized) optimization value for a solu- tion. Let μί±) be the mean value [15] of optimization function f _± :

Let s( fi ) be the adjusted standard deviation [16] of optimi ^¬ zati n function fi (see figure 5.2) :

With the use of the mean value and the standard deviation computed from the set of sample solutions SI ... Sn, we com ^¬ pute the optimization criterion value for an arbitrary new solution Sol (member of feasible solutions S) . The normalized optimization criterion value of an arbitrary solution Sol is then defined by:

f _i (Sol)- (f _i )

norm^f^Sol))

So the normalized optimization value is the raw value shifted by the mean value and divided by the standard deviation. In fact, it is the amount of standard deviations the actual raw value differs from the mean value and therefore a very con ^¬ venient measurement of the quality of a solution. Theoreti ^¬ cally, the range of that new normalization function is , but most of the values will group around the mean value. E.g., about 68% of the values will lie within +/-1 standard devia ^¬ tion around the mean value. Examples:

normif^Sol)) =0 : the normalized value is exactly the mean value

norm(f _i (Sol))=— Q.5 the normalized value is a half standard deviation better than the mean value

norm (f^Sol)) =2.3 : the normalized value is 2.3 standard de ^¬ viations worse than the mean value

Normalized values of different optimization functions can now easily be compared with each other, because they are of the same unit: the standard deviation. If weights wi are used to differentiate between high and less important criteria, the accumulated optimization value for a solution Sol is then defined by: f (Sol) =-^—*∑w _i * norm (f _t (Sol)) i=l

For a concrete combinatorial problem with technically feasi ^¬ ble solutions S i , S _n , the goal is to find the one(s) with minimal or maximal value of f :

min^/CS,.) or max^ /(S,.)

A preferred case of application of the inventive method is product configuration by means of computers.

Product configuration is the task of selecting and combining parts from a parts catalogue and of finding a valid solution which meets all technical constraints, all user requirements, and optimizes several optimization criteria. In case of con ^¬ sumer products, like mobile phones, bicycles, cars, note ^¬ books, etc., typical optimization criteria are: small price (in EURO), small weight (in kg), high reliability (mean time to failure), length of guarantee (in years), "greenness" (e.g., fair produced, fair traded, low C02 footprint) . All the different optimization criteria deal with values of fun ^¬ damentally different unit (e.g. EURO versus kg) and cannot be compared directly.

With the inventive method, as described above, values of dif- ferent units can be normalized to combine them to a standard ^¬ ized optimization function.