GB2474900A - Processing a complex problem using one of a plurality of different solvers - Google Patents

Abstract

The present invention relates to a method and a tool that allows the user to define a complex problem using the tools with which they are familiar but allows the optimal solution to be found using one of a range of different solvers without the user having expert knowledge of the underlying solver. The user defined rules are received in a rules engine 3 and applied to problem data. A common solver problem is generated by a rule adapter 13 in a middleware component 11 using the rules. The common solver problem is then provided to one of plurality of different solver engines 5,7,9 using a respective solver adapter 15. The most appropriate solver 5,7,9 for that problem may be chosen automatically for the user, for example by analyzing the properties of the common solver problem. The rules engine may be business rules engine 19. The solver engines 5,7,9 may be a scheduling engine, an integer programming engine, a mixed integer programming engine, a linear programming engine and a planning engine.

Description

"A method and tool for processing a complex problem"

Introduction

This invention relates to a method of processing a complex problem and a complex problem solving tool.

There are numerous methods and commercially available tools for solving problems. For example, business rules engines, business process modelling and case management tools are used to solve problems. One tool commonly used to solve problems is the business rules engine whereby a user may input certain business rules and process a set of problem data in accordance with the business rules. The business rules engine will if possible provide a solution to the problem. The main advantage of business rules engines is that they are relatively simple to use and often allow entry of business rules in an intuitive manner by relatively unskilled users.

There are however a number of problems with the known business rules engines. First of all, the known business rules engines are typically limited in the type and scope of information that they can process. Secondly, in order to be effective in solving complex problems, the known business rules engines require numerous rules to be applied which r. is time consuming to program and execute. Thirdly, and perhaps most importantly, the known business rules engines usually do not provide the optimal solution to the problem and therefore if it is desirable to obtain the optimal solution to a problem, the business rules engines are often inadequate. Many of the above problems also apply to business process modelling. In particular, when business process modelling is used to create a * new schedule, it would be advantageous to provide an optimised schedule however business process modelling is not naturally disposed to provide such information.

In order to overcome these difficulties, a number of methods and tools directed towards overcoming the shortcomings of business rule engines and in particular the inability of the business rules engines to provide the optimal solution to the problem have been provided. Of these, one particularly suitable method of solving complex problems and providing an optimal solution is constrained programming. Constrained programming enables many different types of complex problems across a wide range of disparate w, 4 technologies to be solved. Constrained programming techniques have been applied in planning, scheduling, resource allocation, assignment, placement, logistics, VLSI design, network management, satellite tasking and data centres to name but a few. The constrained programming techniques permit the optimal solution to a problem to be found efficiently.

There are however problems with the known constrained programming methods and tools. Heretofore, the majority of these tools require highly specialised knowledge of the underlying method and tool to operate. Accordingly, the known methods and tools are usually expensive to implement and are not particularly suited to mass distribution.

Secondly, constrained programming is itself not suitable for all applications and in some instances can take a significant amount of time to arrive at the solution to the problem.

Attempts have been made to provide simplified methods and tools that will enable less skilled users to avail of the benefits of constrained programming techniques. Some of these have proposed the combination of rules and constraints. For example, the papers by Kameshwaran et al, entitled "Multiattribute electronic procurement using goal programming", European Journal of Operational Research, 179, 518-536, 2007; Carlsson et al, entitled "A Geometric Constraint over k-Dimensional Objects and Shapes Subject to Business Rules", Principles and Practice of Constraint Programming, Lecture Notes in Computer Science Springer Volume 5202, pp 220-234, 2008; and Fages and Martin entitled "From Rules to Constraint Programs with the Rules2CP Modelling Language", INRIA Research Report RR-6495, Institut National de Recherche en lnformatique, 2008; all describe ways in which business rules can be translated into constraints and thereafter the problem can be solved with a single technology. However *...

* this is not always desirable as business rules on their own can be used to make decisions using the different technology route of the RETE algorithm.

Another approach is that described in the paper by Bousonville et al entitled "Integration of Rules and Optimization in Plant PowerOps", Principles and Practice of Constraint Programming, Lecture Notes in Computer Science Springer Volume 3524, pp 1-15, 2005. According to this paper, there is provided a method in which business rules are used to generate a data input to a predefined optimisation model. However, this approach is relatively limited in that it does not provide direct access to decision variables so that only predefined constraints are possible. This limits the functionality and usefulness of such a method.

US patent application No. 2008183538 describes a method in which a rules description is converted to a constraints description in a workf low engine. Similar to Kameshwaran, Carlsson and Fages, the problem is solved with a single technology and there are certain circumstances when the best possible result will not be returned, US patent application No. 2008208719 describes a method in which a rules description is used to choose an appropriate constraint model from a limited selection of constraint models.

Finally, W003001 322 describes a hybrid method in which rules are used to define a generic work space without describing all special cases. An optimisation engine is then used to create and analyse all possible branches of the tree specified by the rules to select the best option, or in other words, the optimal solution. The present invention relates to a similar type of method in which both rules and an optimisation technique are used in combination with each other, rather than instead of the other or where one technique is used as a pre-processor or selector for the other technique. However, W003001 322 proposes a 1 to 1 mapping between technologies (rules to constraints) which is relatively limited.

t is an object of the present invention to provide a method and tool for processing a complex problem that overcomes at least some of the problems with the known types of methods.

I

*.,.I.

* . 25 Statements of Invention

S.....

S I

According to the invention there is provided a computer implemented method of processing a complex problem comprising the steps of: receiving user defined rules in a rules engine; applying the user defined rules to a set of complex problem data; 4..

generating a common solver problem from the user defined rules using a rules engine adaptor; providing the common solver problem to one of a plurality of different solver engines using one of a plurality of solver engine adaptors thereby creating a solver engine specific problem; and processing the solver engine specific problem and the set of complex problem data that has had user defined rules applied thereto in the selected solver engine.

By having such a method, both the rules and the optimisation technique will be used in the solution of the problem. The rules are not simply a pre-processing technique or a means of selecting an optimisation algorithm but instead the user defined rules are integral in the dynamic creation of the common solver problem itself which forms part of the optimisation technique. By creating the common solver problem dynamically with the user defined rules, it is possible to thereafter manipulate the common solver problem for use with a number of different solver engines. Therefore, the method is very flexible as a range of different types of solver engines may be used and in this way several disparate technologies may hang off rules. Furthermore, the method allows input in the form of rules and a user may input data into the system in a format with which they are familiar.

The rules are then used in the generation of a common solver problem. This is particularly useful as the user will be able to input data in a format with which he is familiar and it is not necessary for the user to have specialist skill in the optimization techniques.

S. .**S * S The present invention provides a more generic approach than the existing approaches and allows for a wide range of combinations of technologies to be combined in a logical manner. According to the invention, it is possible to select the appropriate solver and produce an appropriate model which will result in the problem being solved either faster or to a higher quality.

In another embodiment of the invention there is provided a computer implemented method comprising the additional intermediate steps of: determining the most suitable solver engine from the plurality of solver engines to process the common solver problem and the set of complex problem data; and providing the common solver problem to the most suitable solver engine.

In this way, the method can automatically determine which of the solver engines is the most suitable for providing a solution to the common solver problem and the common solver problem will be routed to the appropriate solver engine adaptor for that solver engine.

In a further embodiment of the invention there is provided a computer implemented method in which the most suitable solver engine is determined based on an analysis of the properties of the common solver problem.

In another embodiment of the invention there is provided a computer implemented method in which the most suitable solver engine is selected based on an analysis of one or more of: a variable of the common solver problem; * * * a constraint of the common solver problem; and * .** the type of activity of the common solver problem. * 25

** ** ** * In this way, the rules will define the variables and the constraints of the common solver problem and once the common solver problem has been generated, it will be possible to determine which solver engine is most appropriate and the common solver problem may be directed to the appropriate solver engine adaptor so that the solver engine specific problem may be created and thereafter solved.

In one embodiment of the invention there is provided a computer implemented method in which the user defined rules comprise at least one user defined rules' variable which in turn is used by the rules engine adaptor to create a variable of the common solver problem.

In a further embodiment of the invention there is provided a computer implemented method in which the steps of generating the common solver problem, providing the common solver problem to a solver engine and processing the solver engine specific problem are performed each time a particular user defined rule is qualified during application of the user defined rules to a set of complex problem data.

In another embodiment of the invention there is provided a computer implemented method in which a further rule is applied to the complex problem data prior to processing the solver engine specific problem each time the particular user defined rule is qualified.

In one embodiment of the invention there is provided a computer implemented method comprising the additional intermediate step of analyzing the common solver problem and reformulating the common solver problem.

In a further embodiment of the invention there is provided a computer implemented method in which the method comprises the intermediate step of selecting one of a plurality of rules engine adaptors to generate the common solver problem depending on the rules engine.

** In one embodiment of the invention there is provided a complex problem solving tool * : comprising: * a rules engine for receiving user defined rules; ** S. * . * a plurality of different solver engines; a middleware component intermediate the rules engine and the plurality of different solver engines, the middleware component comprising: a rules engine adaptor for generation of a common solver problem using rules from the rules engine;

-I

a plurality of solver engine adaptors, one for each different solver engine, for generation of a solver engine specific problem from the common solver problem.

By having such a tool, it will be possible to solve complex problems in a simple and effective way. A number of different rules engines may be selected. Furthermore, the user may input data into the system in the format of business rules or the like and these rules are then used in the generation of a common solver prob'em. This is particu'arly useful as the user will be able to input data in a format with which he is familiar and it is not necessary for the user to have specialist skill in the optimization techniques.

In a further embodiment of the invention there is provided a complex problem solving tool in which the middleware component comprises an analyzer for analyzing the common solver problem and determining the most suitable solver engine for the common solver problem.

In a further embodiment of the invention there is provided a complex problem solving tool in which the middleware component comprises means to reformulate the common solver problem. * * *

In another embodiment of the invention there is provided a complex problem solving tool in which the solver engines comprise a constrained programming engine.

*e.**.

* . 25 In another embodiment of the invention there is provided a complex problem solving tool I. S e * in which the solver engines comprise a plurality of constrained programming engines. ** S. *

In a further embodiment of the invention there is provided a complex problem solving tool in which the solver engines comprise one or more of a scheduling engine, an integer programming engine, a mixed integer programming engine, a linear programming engine and a planning engine.

In one embodiment of the invention, the solver engine comprises a case-based reasoning engine. It is envisaged that the case-based reasoning engine would not perform optimisation however the case-based reasoning engine would enhance rules and the like inputs when provided with a generic problem description.

In another embodiment of the invention there is provided a complex problem solving tool in which the rules engine comprises a business rules engine.

In one embodiment of the invention there is provided a complex problem solving tool in which there are provided a plurality of rules engines and a plurality of rules engine adaptors.

In a further embodiment of the invention there is provided a complex problem solving tool in which there are provided a plurality of business rules engines.

In another embodiment of the invention there is provided a complex problem solving tool in which the rules engines comprise one or more of a business process management engine, a business intelligence engine and an enterprise decision management engine.

In one embodiment of the invention there is provided a complex problem solving tool in which there is a single modeling environment in which all of the solver engines are represented at the same level. a... * a *

In a further embodiment of the invention there is provided a complex problem solving tool in which the analyzer uses a case based reasoning technique to determine the most suitable solver engine for the common solver problem.

at....

In another embodiment of the invention there is provided a complex problem solving tool in which the rules engine adaptor comprises an integration library.

In one embodiment of the invention there is provided a computer program comprising program instructions for causing a computer to carry out the method.

In a further embodiment of the invention there is provided a computer program product having the computer program stored thereon.

eailed Description of the Invention

The invention will now be more clearly understood from the following description of some embodiments thereof given by way of example only with reference to the accompanying drawings, in which:-Figure 1 is a diagrammatic representation of a first embodiment of hybrid complex problem solving tool according to the present invention; Figure 2 is a diagrammatic representation of a rule description interface; Figure 3 is a diagrammatic representation of a constraint description interface; Figure 4 is a diagrammatic representation of a rule used to add a variable and constraint of the common solver problem; Figure 5 is a code segment showing rules passing information to the solver engine; Figure 6 is a diagrammatic representation of machine compatibility sets; S...

*:.. Figure 7 is a screen shot showing the status of all machines before and after the implementation of the method according to the invention; * S0 SS* * 25 Figure 8 is a screen shot showing the status of all machines before and after the * S implementation of the method according to the invention; and S. * S * Figure 9 is a screen shot showing the status of all machines before and after the implementation of the method according to the invention.

Referring to the drawings and initially to Figure 1 thereof, there is shown a complex problem solving tool, indicated generally by the reference numeral 1. The complex problem solving tool comprises a rules engine, in this case business rules engine 3 for receiving user defined rules and a plurality of different solver engines 5, 7, and 9. In the embodiment shown, the rules engine 3 comprises an OpenRules engine and the solver engines 5, 7, 9, comprise a Choco solver, a Constrainer solver and an ILOG solver. The Choco solver, Constrainer solver and ILOG solver are all constrained programming solver engines. The complex problem solving tool further comprises a middleware component 11 which in turn comprises a rule engine adaptor 13, a solver engine adaptor and an analyzer 17.

In use, user specified rules are received in the rules engine 3. OpenRules provides an Excel application interface so that rules may be inserted in a spreadsheet format. These rules in the Excel format are applied to a set of problem data (not shown) and are converted by the rule engine adaptor 13 into a common solver problem. In the present invention, the common solver problem is in Java programming language. The common solver problem comprises one or more variables and one or more constraints for the constrained programming solver engine 5, 7, 9. The analyzer 17 then determines, based on an analysis of the properties of the common solver problem, namely the variable and the constraint, which of the constrained programming solver engines 5, 7, 9 is most suitable for solving the problem. The analyzer uses case based reasoning in the determination of the most suitable solver engine 5, 7, and 9. Once the most suitable solver engine has been determined, the common solver problem is then provided to the solver engine adaptor 15 (only one of which is shown) corresponding to the most suitable solver engine. In the solver engine adaptor 15, the common solver problem in Java code is taken and modified into a solver engine specific problem, or in other words a model, suitable for processing in whichever of the solver engines 5, 7, 9 was determined to be the most suitable. The solver engine specific problem is then processed with the set of complex problem data that has had the user defined rules applied thereto. *::: *

In order to create the model it is necessary to determine the following three items: 1) what are the decision variables; 2) what are the restrictions on these decisions and 3) ** .S * 30 how do you calculate the cost of a solution (once all the variables have a value).

Depending on the type of variable, whether it is a type integer or a type real, and the nature of the constraint which depends on the choice of variable, i.e. whether it is linear * . * * or non-linear, then an appropriate solver can be identified. This is done automatically by the middleware component 11 as it knows the type and linearity of the problem that have been defined. Cost is similar to a constraint in terms of linearity. Therefore, if the variable is real and the constraint is linear, an LP solver will be chosen. If the variable is an integer and the constraint is linear, an IP solver will be chosen (although CP can also handle this, but empirically less efficiently). If the variable is an integer and the constraint is non-linear, a CP solver will be chosen.

There is a 4th stage which configures how the solver is to perform -the internal choices it has to make. The CP and IP solvers work on the basis of building a search tree. How this search tree is built (strategy) determines how quickly a solution is found and how quickly it proves optimality. Both CP and IP solvers build a search tree based on the choice of a variable at each node and the order n which each branch is developed from that variable. In CP, each branch from a node corresponds to assigning a different value to that variable. In IP each branch corresponds to putting on an additional constraint.

Which variable to choose and the order in which to develop from that node defines a search strategy. This is the basic type of search strategy in CP and IP, but there are many others. For example in CP there are different levels of propagation you can switch on/off, while in IP there are tests for additional cuts (constraints) which can be chosen or not. LP solvers are much more of a black box technology for the user. Here a variety of switches are provided to choose different algorithms to find an initial feasible solution and then iterate towards optimality.

It is possible at the outset to opt for a different basic model. Often this choice will be between a Constraint programming (CP) model and an Integer programming (IP model).

Both of these models deal with integer variables, but CP has several high level constraints which are non-linear or at least would require a large number of linear constraints which is disadvantageous when dealing with an IP solver. For small models, *..S *** : less intelligence is needed as they will tend to find a solution regardless of how bad the * .** choices that are made in the selection of the model. * ** .*

* 30 In addition to the components outlined above, the complex problem solving tool 1 is shown to comprise a further business rules engine 19, in this case Drools, a business process management engine 21 and associated adaptor 23, a business intelligence * engine 25 and associated adaptor 27, an enterprise decision management engine 29 and associated adaptor 31, a pair of mixed integer programming solver engines 33, 35, -12-one of which 33 is a CPLEX solver engine and the other of which 35 is a ojAlgo solver engine. Each of the mixed integer programming solvers 33, 35 has an adaptor 37 (only one of which is shown) associated therewith. A linear programming solver engine 39 and associated adaptor 41, a solver engine 43 and associated adaptor 45 and finally a planning solver engine 47 and associated adaptor 49 are also provided. Once again, all of these components or a combination of all of these components may be provided depending on the requirements of the user and the deployment of the tool. For example, in some environments, there may be a need for a single rules engine such as a business rules engine whereas in other environments there may be a need for several rules engines to be accessible. For example, if the invention is put into operation in a large organization or over the internet with software as a service, the users of the invention may have numerous ways of entering data into the tool.

Constraint programming is based on the notion of variables and constraints. However, sometimes it is more convenient to think in higher level terms. For example, as well as convenience, constraint programming may also improve efficiency as it allows specialised reasoning algorithms that can exploit additional knowledge to be used.

For a scheduling problem, the notions of resources (e.g. a machine, or capital, or a technician) and tasks (e.g. a batch of products that is to be produced) as well as a new constraint describing that a certain task requires a certain resource (e.g. this batch is to be produced on or requires a machine of a particular type). Each of these entities encapsulates a number of variables (e.g. start time, duration, and end time for the tasks), as well as some internal constraints (e.g. start time + duration = end time).

The specialised reasoning algorithms come into play when there are a number of tasks S. 1* assigned to a resource, and it is necessary to establish the times at which these tasks *.** **, will be executed. For example, consider two tasks that each take two hours to complete and cannot be interrupted mid way through the task. Task 1 has to be finished before time hour 10, and task 2 has to be finished before time hour 3, but can only start at time hour 1. The algorithm (which is called the "cumulative constraint") will recognise that this means that task 1 cannot start before time hour 3, even though it is allowed to. The reason is that task 2 occupies the resource between time hour 1 and hour 3, and task 1 coes not fit before that (as it requires two hours). Some constraint solvers such as hog and Choco take these concepts into account. If the constraint solver takes these concepts into account, these implementations can be used directly instead of the implementation of the complex problem solving tool according to the invention. However, if the underlying solver does not support these concepts, the complex problem solving tool will recognise this and use its own implementation instead.

The invention will now be described in more detail by way of a few examples of the implementation of the method according to the invention. There follows several hybrid approaches to solving a resource reallocation problem, where it is shown that different technologies can work closely together to solve a problem in an elegant, efficient manner. By allowing the technologies of Constraint Programming and Mathematical Programming to be integrated through the middleware layer to Business Rules, this increases the ease of harnessing the power of diverse, but complementary technologies.

The specific problem being addressed is in the area of dynamic machine utilisation, for example in a data centre where each machine is effectively a memory storing data. This example is one which naturally breaks down into determining which machines within the data centre exhibit performance difficulties and then reallocating the workload across a subset of the machines, to provide a better performance profile. The solving methodology allows us to use Business Rules technology to define the problem and to build an appropriate model for the Constraint Programming technology with the optional assistance of Mathematical Programming to solve for an optimal reassignment of work.

The data centre has a number of machines executing different tasks over time. The number of tasks on each machine is uncertain as the scheduling is done automatically using dispatch rules. It is felt that a balanced workload is desirable to prevent certain machines being overused and hence accelerating their required maintenance and * S * downtime frequency. Sensors attached to the machines continually monitor * ***** characteristics of the machine which indicate how much "stress" the machine is under * (e.g. temperature, rate of output, power usage, number of tasks, utilisation, etc). *I

* 30 Consequently, some machines may become over used and at risk of breaking down. To address this problem, a set of rules, based on sensor information, is used to identify which machines are at risk. These rules identify situations, developing over time which * should be conveyed to the operator as a classification of very high, high, medium and liw risk machines. The operator then has to find a way of reallocating the work to try and alleviate the problem of machines at high risk. This is the problem we are concerned with in this example. Although there is no direct relationship between stress and utilisation it is a good enough indicator and by moving tasks we change the utilisation and hence remove or increase "stress". There are, in addition, certain restrictions of how the workload can be redistributed. For certain machines there is a restricted set of other machines their workload can be transferred to. Overall we seek to generate a re-distributed workload across all the machines with as few changes as possible.

There are two ways in which there will be provided a description as to how to solve this problem. Both ways recognise and promote the need to combine technologies in innovative ways to obtain a straightforward model and a fast solution. The first approach comprises a pair of stages. First of all, there is an identification stage and then there is an optimisation stage. In step one, the identification of machines that are at the different risk levels and the formulation of the re-distribution problem is carried out. In step two, there is provided an optimisation stage which generates a new workload allocation with as few changes as possible.

The first step, identifying the level of risk associated with each machine, uses business rules to examine the sensor history of each machine. The machine risk classification rules are shown in figure 2, within an Excel (Registered Trade Mark) table, indicated by the reference numeral 61. The Excel table is the input medium for the Rules engine.

These rules describe the conditions for a machine to be at low, medium, high and very high risk state. The machine condition is default to low unless a rule raises it to a higher state.

For example, the first rule 63 states that a medium risk machine is one which has spent * *** : 40% or more of its total time above a 45% utilization level. The second rule 65 states that if there is a maximum utilization at or above 60%, when the utilization is being **** checked at intervals of at most every ten minutes, then the machine risk is classified as 30 high risk. The third rule 67 states that if there is a maximum utilization at or above 70% when the utilization was being checked more frequently than every ten minutes, then this machine is classified as high risk. The fourth rule 69 states that if there are three or more ** *** : * consecutive utilisation readings above 70%, when the utilisatiori was measured more frequently than every fifteen minutes, then it is classified as very high risk. The fifth rule -15- 71 states that if there are two or more consecutive utilisation readings above 70%, when the utilisation was measured at most every 15 minutes, then the machine is classified as very high risk. Finally, the sixth rule 73 states that f there is any reading above 70% when the utilisation is measured at most every thirty minutes, the machine is classified as very high risk. Since there are possibly multiple firing rules, the rules are triggered from top to bottom and each will override earlier rules if it is triggered. Thus the last rule that gets triggered will assign the machine the maximum risk level.

The middleware engine 11 provides the facility to describe constraints within the Business Rules environment and to add them into the constrained programming model.

Therefore, the user is able to describe through the same rules interface, the constraints on utilisation, indicated by the reference numeral 81, and as shown in Figure 3. The constraint is to set the maximum utilisation to be either 60 or 70 depending on what the sampling frequency has been. Constraint 83 sets the maximum utilisation to be 60% when the sampling frequency is at most every 10 minutes or more. Constraint 85 sets the maximum utilisation to be 70% when the sampling frequency is every ten minutes or less.

At the problem identification stage, the complex problem solving tool and method also starts to build the features of the optimisation model in terms of the constraints and the variables. The method introduces a certain amount of intelligence in building of the constrained programming model, since in some cases it is preferable to limit the number of machines to consider in the solution. It is necessary to include all the machines which are at very high risk (or above the maximum utilisation level defined in Figure 3), and also those machines which are currently below a certain utilisation, based on the historical maximum utilisation. For every very high risk machine with a set of optional * machines for reallocation, these optional machines for reallocation are added in for * .** **,** consideration.

I 1*11

* 30 Referring to Figure 4, there is shown a table, indicated generally by the reference 91, *: comprising a rule 93 related to which machines to consider for reallocation of resources.

The rule 93 stipulates that only those machines with a usage level of less than or equal : * to 15% of their total capacity will be allowed for reallocation. The rule is intended to check whether or not a machine is relevant to the problem (either it is above the usage threshold and needs to be reallocated, or else it is below the "highest usage machines to add to model" limit and a good candidate for adding to the problem model as it has a lot of tree space). The rule checks if the machine satisfies either of those conditions, and if it does it is added to the problem, and a max utilization constraint is placed upon it, constraining it to not have a utilization above the usage threshold. The value 0 is (as indicated by the variable name dummyValue) merely a placeholder value to make sure that Openrules parses the entire rule (without any value there, the p.addConstraintMachineMax(m,limit); above would not be invoked).

Referring to Figure 5, there is shown a piece of Java code, indicated generally by the reference numeral 101, created by the rules engine adaptor 13 which adds the variable representing this machine to the constrained programming model. By "this machine, what is meant is the machine which satisfied the condition of the RelevantMachineRules rule, for example, either the machine was above the usage threshold, or below the low usage limit as indicated above. Both machines with a lot of free space and machines with excessive usage are added. Any machine that satisfies either of those conditions has that piece of Java code run on it to add it to the common problem model.

Referring to Figure 6, the rule and the compatible machine sets are shown, indicated generally by the reference numeral 111. These type of constraints, ones where the additional load can only be transferred on to certain predetermined machines, make the problem significantly more difficult.

Referring to Figures 7 to 9, there are shown various screen shots showing the status of all machines before 121, 131, 141 and after 123, 133, 143 the implementation of the method according to the invention. It can be seen from the machine status screen shots . that before the implementation of the method, six machines 125 are at very high risk and two further machines 127 are at high risk. The remaining machines are at low or medium risk. The optimisation problem relates to finding a suitable redistribution of work which *.** SI reduces the very high risk machines 125 and the high risk machines 127 to below a specified level, while affecting the minimum number of machines to accommodate this.

:* * In all of the figures 7 to 9, "high risk" is utilization equal to or over 60%. When a solution * is found, the max utilization of any machine is limited to be exactly 60%, not higher. So in Figures 7 to 9 for results, the dashed boxes that repesent the high risk machines 127 remain dashed boxes even though they had their utilization reduced, from something above 60% to exactly 60%.

In this example, we assume that work is simply a percentage and reflects the utilisation of the particular machine. Therefore, a machine having 50% utilisation is handling 50 units of work, some or all of which could be passed, in the same units, to another machine if this is desired. Here we do not model individual tasks, but assume that tasks can be subdivided across machines in discrete amounts of a single unit (i.e. work can be transferred in one percent amounts). The final decision as to what specific tasks are redistributed is left to the planner, the model simply indicates the feasibility and new allocation of work.

The model is built around a set of variables representing the utilisation of each machine.

The value this variable can have is an integer between 0 and 100. The constraints are: 1. an upper bound on the utilisation of any machine and 2. a restriction as to which set of machines, one machine may redistribute its work.

The objective is to find a redistribution of work with the minimum number of changes to the workloads of the machines. The magnitude of the change is not considered as it is believed that the overhead of just making a change is more important than the quantity of the change.

The search chosen is based on first trying to find a solution with a lower bound of changes. The lower bound is taken as the number of machines at very high risk level plus 1 (in other words if the excess work on all the very high risk machines could be I. redistributed to a single machine). If unsuccessful, the search then increments this counter until a first solution is found. This by implication is the optimal solution. * .**

30 With the number of machines totalling potentially over 100, the chances of finding and *.** 4 proving optimality are quite small. With the search strategy adopted a lot of searching will have to take place to prove infeasibility since there is a high degree of symmetry.

** **.

* Instead the approach proposed here is that a smaller model is generated, depending on the size and nature of the problem defined by the rules. It is envisaged that a small problem will find better solutions within the solving time than a larger model, using the same search strategy.

A comparable technology that may be used in place of Constrained Programming (CP) in this instance is an Integer Programming (IP) solver 33, 35, accessible through the middleware engine 11 and the solver engine adaptor 37. However, the objective of minimum number of changes is not one which naturally linearises for use with lP. In this instance CP was chosen as the first technology option.

The experimental data shows the different qualities of solution and time it takes to find these solutions depending on the constraints app'ied. Four separate scenarios are described below. In scenario 1, all machines are considered in the model for redistribution of resources to those machines and a solution is sought with a minimum number of changes. The results are shown in Figure 7. When the method was not optimising but merely searching for any solution whatsoever, the search took under 1 second. The result without seeking optimal results is five changes, four of the machines shown in the bottom right hand corner of screenshot 123, became high risk machines 127, and one further machine had a slight change though it remained low utilization. The optimisation model did not succeed in finding a solution minimising the changes after fourteen hours and a significant amount of time was spent processing the various options.

In scenarios 2 to 4, the model incorporated the model reduction rule whereby the rule selected only those machines for inclusion into the model, which were at very high risk or currently below 15% utilisation. *...

In scenario 2, illustrated by Figure 8, the problem has no objective, but is simply to find I. the first solution which satisfies all the constraints. The result is that 3 changes to non-excessive machines were made in less than 1 second. The result is shown in Figure 8, * 30 screen shot 133 where all machines are now at either high risk or lower. Three *: machines represented in the lower right hand corner of the screen shot have had work redistributed to them, two 127 of which are now at high risk and one 129 of which is at * medium risk, as the resources from the six very high risk machines 125 and the two high risk machines 127 have been transferred to these three machines 127, 129.

In scenario 3, illustrated by Figure 9, the model has the objective of finding the smallest number of changes (in other words, with optimisation). The result is that three changes were made to non-excessive machines. The solution time was also approximately 1 second. Three machines represented in the lower right hand corner of the screen shot have had work redistributed to them, two 127 of which are now at high risk and one 129 of which is at medium risk, as the resources from the six very high risk machines 125 and the two high risk machines 127 have been transferred to these three machines, 127, 129.

In the present examples, the performance of scenario 2 is identical to the performance of scenario 3. In other words, the scenario without optimisation found the same results as the scenario with optimisation in models with the reduction rule. In general, this will not be the case and scenario 2 and scenario 3 will not always give the same solution. The results of scenario 2 will usually be worse than the results of scenario 3 however in this particular example they achieve the same result.

In scenario 4, the problem has two additional compatible set constraints in which the overflow of work from some machines can only be transferred onto a limited set of other machines. The results are four changes to non-excessive machines were made. The running time was approximately 5 seconds. The increase in running time can be explained by the failure driven search used. The failure driven search proceeds by trying to find a solution with one change and on failing proceeds to 2 changes and so on. With the additional constraints, the search is extended from 3 to 4 changes and accordingly the search takes longer. *

The above results from scenarios 1 to 4 inclusive show that it is possible to obtain * .** solutions and indeed optimal solutions provided that the model size is reduced.

Secondly, the quality is not compromised through model reduction. If additional constraints are added, the time to find a solution increases while the quality of optimal solution decreases.

The second approach is described through two inter-leaving stages: -20 - 1. As each machine is sequentially identified as high risk using the rules definition, a small local problem is created and modelled, but within a restricted set of machines close to' to the high risk machine. This is then passed to a second optimisation stage.

2. An optimisation stage which generates a new workload allocation with as few changes as possible.

This approach is particularly relevant where the presence of high risk machines is fairly sparse and there is the opportunity to create several small problems. In some instances, the locality of the re-allocation is also a consideration. Therefore it is not always the fewest moves that is sought, but sometimes it can be to keep the moves nearby due to certain overheads of moving through distance. This is a local approach where only solutions in a restricted area are sought and thus make the problem smaller. The method starts at numerous times at defined points, determining a neighbourhood from that point (through rules) and searches within that region using CP. Again there is the same type of constraints and objective function. The only difference is in the additional neighbourhood rules defined to describe what size of local problem to create.

In order to identify and create the problem, this follows much the same process as described above. However, there are some further problem creation rules. These rules define the neighbourhood' of machines from the high risk machine that the workload can be reassigned to. If there is any overlap of machine sets in the problems, the updated values from the first local search are used as the starting values in the second problem model.

When applied to the scenario 1 data set, there are eight excessive machines with either 0*' high or very high risk. This approach results in eight local problems being solved, each making one change and resulting in eight non-excessive machine changes overall.

30 In one embodiment, it is possible to introduce a Simplex Algorithm for optional search reduction. The introduction of the Simplex algorithm within the CP search to model and solve a related problem can reduce the time spent in proving infeasibility. The search within approach 1 proceeds by trying to find a re-allocation with increasing number of moves. Therefore much of the search time is spent determining infeasibility. The -21 -hypothesis is that the Simplex being a very fast algorithm will detect infeasibility quicker even though it is on a more relaxed problem. If we consider only the restricted sets constraints, we check to see if there is enough capacity among the possible alternative machines. This is not trivial since an under-utilised machine may be expected to take workload from a number of high risk machines. This can be modelled as a sort of capacity flow problem. If we cannot redistribute the flow, then there no point trying to find a solution whatever number of moves.

In the case of a data centre, it would be possible for every problem disk and its compatible set of disks, to create a flow variable for each link. We know that there is a flow of X out of the problem disk to all the others. Repeat this step and solve. This can be quicker than other implementations.

It will be understood from the foregoing that combining rule and constraint solving engines together has been achieved through the method, the complex problem solving tool and in particular the middleware component 11. The middleware is a three layer framework which allows different constraint solvers 5, 7, 9 or mathematical programming solvers 33, 35, 39, 43, 47 to be plugged into a standard model description which in turn is invoked through a number of integration libraries. The libraries are accessed through a single Java API. In the present invention, the integration library is to the Business Rules package of OpenRules 3 through Excel, which is its own interface to the rule definition language. A Technical User (not shown) can define the optimisation model in the middleware 11 as a Common CSP model and deploy the common CSP model using the interface library to OpenRules. The tool and middleware also provides adaptors 15, 37, 41, 45, 49 to a number of constraint solvers so that a model defined in the middleware can use a variety of solvers depending on the requirements of performance and * **1* licensing. *

The integration of rules and constraint based optimisation technologies through the 30 present invention creates a platform which allows the development of a variety of solving *" configurations. These configurations are capable of solving complex problems which require a mixture of approaches. Making these approaches fit together easily is the first requirement for a successful decision making technology. The present invention provides the middleware to bring Constraint programming into different business tools -22 -environments and be accessed easily from there. The specific application discussed above demonstrates the need for taking an integrated approach to solving a complex problem, which can be solved by appropriate decomposition. The problem in question is illustrative of the implementation of the present invention. It will be understood that more complex problems with additional side constraints and more complex risk conditions would justify the approach more. For Business Rules finding an optimal solution is problematic and could conceivably lead to many rules which are difficult to maintain. For Constraint Programming the creation of the instance of the problem model would require much programming. By passing each challenge to a different technology and linking them together at a low level delivers a fast, easily maintainable solution. Furthermore, for Business Rules users, this gives them access to an optimisation technology without leaving their natural problem description environment.

By implementing the present invention, there is provided a single interface to many underlying solvers. This prevents the users being required to learn the unique interfaces to each of these solvers. In order to provide such a tool, a thorough understanding of the solvers is required and also for some of the more complicated underlying solvers functionality various modifications had to be performed to operate correctly. For example, a methodology for handling goals had to be devised. Goals are objects for recursively defining the search strategy of a solver. The present invention provides a way to automatically generate a solver-specific goal from any (possibly user-defined) goal at the interface's level.

Furthermore, by implementing the present invention, the model is tracked and analysed by the type of variables, type of constraints and type of activities which allows the tool to predict what solving technology would be suitable. The invention provides a single 0** *,.. $. modelling environment where CP, IP, LP, scheduling activities and planning processes are all represented at the same level. In addition, the single modeling environment gives access to multiple solvers of each type (e.g. 3 CP solvers) without the user being 30 required to remodel their problem, as would otherwise be the case. This allows the unskilled user to automatically benefit from the strengths of a type of solver suited to the type of problem they have modelled, and if they choose to, to easily swap between * solvers of that same type to find which will give them optimal performance.

The technical challenges of the present invention were to be able to create dynamically an appropriate model through reasoning with rules. In other words, the model is not given initially, but through running the rules the appropriate number and type of variables as well as the appropriate set of constraints are provided and imposed respectively.

Rules can also run various other optimisation solvers (LP) to decide the type of model to generate (or even whether or not to generate one -it is possible to perform a fast feasibility check on the linear parts of the problem using LP, and if there is no solution to that sub-problem it is possible to deduce the entire problem has no solution too).

There are a number of ways in which the common solver problem may be reformulated.

One way of reformulating the common solver problem would be to create a Linear Programming (LP) model using rules to test for infeasibility. If infeasible then either the tool will give up due to the tact that there is no solution or enlarge the search space. If the search space is enlarged and the common solver problem is now feasible, then this enlarged search space is used as a lower bound and the tool then proceeds to apply constrained programming (CP). One way of reformulating the common solver problem would be to reformulate the problem into a relaxed' linear problem and solve the problem with LP to give us a lower bound or detection of infeasibility. By relaxed what is meant is making an integer variable into a real variable. In this way, the non-linear constraints could be transformed into piece-wise linear or some lower bound equivalent which facilitates processing.

In order to implement the invention and allow relatively unskilled users implement the constrained programming and like techniques, various modifications had to be made to the user defined goals received by the middleware. For example, referring to a user defined goal as an i-Goal and a solver specific goal as an s-Goal, normally, a i-Goal is a :::.: wrapper for a s-Goal, it contains a pointer to the s-Goal and when execute() is called, it will invoke the s-Goal's equivalent of the execute() method. After execution, if there are any subgoals (these are wrapped as i-Goals too) it returns these to the process that S.....

* 30 invoked the executeo call. This is how the tool works when there exists an s-Goal for the * goal we are using. However, when we implement a custom i-Goal which has no solver implementation (no direct/obvious s-Goal equivalent) the tool has an execute() method which does not rely on the s-Goal (it still points to one though) and the s-Goal is a peciaI goal (implemented by the programmer in the adapter) which tells the solver to -24 -run the i-Goal's execute� method when it is executed. i.e. the reverse of the normal case in a way. If the i-Goal's execute() returns subgoals (of type i-Goal) the implementation s-Goals of these subgoals are returned by the s-Goal when it is executed (these may also be the special s-Goal for custom i-Goals too).

In order to create a solver specific goal from any goal at our interface's level, there is provided a method called "goalThisO" which is used when creating the custom i-goal, and it sets its implementation s-Goal as the special goal as described above. The same s-Goal is used for all custom CPI-Goals without need for modification.

One of the advantageous aspects of the present invention is the approach taken as a whole. More specifically, the aspect of having the java classes as "wrappers" for the underlying solver classes is particularly advantageous. This property and careful management of it allows objects to be built at a middleware level out of the wrapper classes, and automatically have them function with the underlying solver, since they works at the middleware level but translate all the necessary low level details (via the wrapper classes) to the underlying solver.

The entire scheduling suite of functionality is provided at the middleware level, as the objects in the scheduler (resources, activities) are defined in terms of the low level wrapper classes for integer variables, so any underlying solver with integer variables (i.e. every solver) can perform scheduling using the resources and activities defined at the middleware level.

One of the main advantages of the present invention is that the user does not have to remodel their problem, as would normally be required. In order to achieve this, the complex problem solving tool and method have provided a single input language to model in, which the complex problem solving tool according to the invention automatically translates into the language of any of the supported underlying solvers.

* 30 Thus to change the solver being used, the user merely needs to change one line, which * states what solver is being used, and nothing more. The complex problem solving tool translates the rest of the code into the new solver's language automatically This "translation" is achieved by creating wrapper classes around the underlying solvers' asses which allows us to interact with the objects and also to add things at the -25 -middleware layer which can be used by the underlying solver, since anything created from the middleware objects is indirectly a creation of the underlying wrapped solver-specific objects too.

In the embodiments described above, the step of running the rules cause the variables and constraints to be created. In order to achieve this, essentially the body of the rule (that part that gets invoked once the condition has been satisfied) calls a piece of Java which in turn calls the Java API to the middleware which in turn creates a variable in the model or adds a constraint to the model. This is illustrated by Figures 4 and 5 of the drawings. Figure 4 shows the rule for determining whether a machine should be added as a variable in the problem or not whereas Figure 5 shows the code for adding the variable. All of the machines are checked by the rule, and those that satisfy the rule invoke the Java code which adds a machine.

Within the complex problem solving tool according to the invention, it is possible to build two different models and solve them using different solving engines. A problem may have two different pieces where the solution of one piece goes into the model of the second. One example of this is illustrated by the re-distribution application. In this example, it is possible to test the feasibility using linear programming and if it suggests that it is feasible then the method proceeds and solves the problem using constrained programming. CP can spend a lot of time trying to find a solution when none exists. A relaxed version of the problem can be solved very quickly using LP and so to save time in trying, LP is tried first. If it is deemed infeasible, the method will cease trying and will go back and reformulate a new problem which may be feasible.

The tool and method according to the invention allows solving engines to be intelligently mixed depending on circumstances which can be dynamic or static. By dynamic or static, what is meant is whether we know the problem at the start or whether we find out about it through user input or from a changing environment. LP is in general a lot faster *.S...

* 30 than CP, but to be able to use LP to solve a problem it must have only linear constraints.

** **** * When there is a problem containing both linear and non-linear constraints, we can take just the sub-problem containing only the linear constraints of the problem, and try to see if that sub-problem has any solution very quickly using LP. If there is no solution to that we know there is no solution to the whole problem either.

-26 -Throughout the specification, the terms "rules" and "rules engine" and variations thereof have been used in both a specific sense and a general sense. When used in a general sense, the term "rules engine" is deemed to include any one of a rules engine, a business process management engine, a business intelligence engine and an enterprise decision management engine. The rules engine, business process management engine, business intelligence engine and the enterprise decision management engine are also collectively referred to as advanced business modelling tools as well as simply "rules engines". "Rules" when used in a general sense, will be understood to be an input to any of the advanced business modelling tools.

The present invention provides an integrated suite of libraries for optimisation, scheduling and planning techniques, which are accessed through a single Java API.

Much of the selection of the correct optimisation methods is automated within the middleware. For more complex problems, the API allows advanced users to dictate all aspects of the optimisation model and the way it is solved. Specifically, one can easily integrate several techniques together where the problem naturally decomposes into different sub-problems.

It will be further understood that the method according to the present invention will be performed largely in software and therefore the present invention extends also to computer programs, on or in a carrier, comprising program instructions for causing a computer to carry out the method. The computer program may be in source code format, object code format or a format intermediate source code and object code. The computer program may be stored on or in a carrier including any computer readable medium, including but not limited to a floppy disc, a CD, a DVD, a memory stick, a tape, a RAM, a ROM, a PROM, an EPROM, a hardware circuit or a transmissible carrier such as a carrier signal when transmitted either wirelessly and/or through wire and/or cable.

*.I...

* 30 In this specification the terms "comprise, comprises, comprised and comprising" and the * terms "include, includes, included and including" are all deemed totally interchangeable and should be afforded the widest possible interpretation. The invention is in no way limited to the embodiment hereinbefore described but may be varied in both construction

and detail within the scope of the specification. -27-