Software tool for iiueristic search methods

• US 20040049479A1
• Filed: 07/09/2003
• Published: 03/11/2004
• Est. Priority Date: 01/09/2001
• Status: Active Grant

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Dorne, Raphael, Voudouris, Christos
• Granted Patent: US 7,406,475 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

This invention concerns a problem modelling tool for building a model of a problem that involves a plurality of variables, whereby a heuristic search method can be carried out to optimise a solution for the modelled problem, and wherein the model of a problem comprises a plurality of expressions defined as corresponding one or more declarative statements and at least some of the expressions are dependent on at least one of said variables. In embodiments of the invention, the problem modelling tool includes means for automatically updating the, or each, declarative statement in response to changes to the or each variable associated therewith.

Claims

1. A method of optimising allocation of resources for a resource allocation problem, the problem being defined by problem variables, problem expressions, problem constraints and an objective function to be optimised in accordance with a predetermined optimisation criterion,

wherein the problem variables are representative of at least some of resources to be allocated, temporal parameters associated with allocation of the resources, tasks to be performed, costs associated with allocation of resources, capabilities of the resources and capacity of the resources,

the problem expressions are representative of relationships between the problem variables, and

the problem constraints are representative of constraints placed upon the problem variables,

the method comprising the steps of

i. building a model of said resource allocation problem in accordance with said problem variables, problem expressions, problem constraints, and objective function,

ii. generating a solution to the modelled problem, the initial solution comprising a set of values representative of at least some of the problem variables,

iii. applying a change to the solution by modifying one or more values in the set,

iv. identifying problem expressions directly and/or indirectly dependent on the modified values,

v. of the dependent problem expressions identified at step (iv),

a. selecting an identified problem expression from the dependent problem expressions identified at step (iv),

b. evaluating whether one or more inputs to the selected problem expression has changed,

c. if the or each input has not changed, marking the selected problem expression, and all problem expressions dependent on the said selected problem expression as unchanged,

d. selecting the next problem expression identified at step (iv), and

e. repeating steps (b)-(d) until there are no further problem expressions to be selected.

2. A method according to claim 1, wherein, if the input has changed, the method further comprises evaluating the selected problem expression and evaluating all problem expressions directly and indirectly dependent on said selected problem expression.

3. A method according to claim 2, wherein the method further comprises assessing whether the objective function satisfies the predetermined optimisation criterion as a result of the change applied at step (iii), and, if not, repeating step (iii) until the objective function is deemed to satisfy the predetermined optimisation criterion.

4. A method according to claim 2 or claim 3, wherein evaluating whether an input to the selected problem expression has changed comprises recursively identifying and evaluating inputs to the input.

5. A method according to any one of claims 2 to 4, wherein evaluation of the selected problem expression comprises the steps of:

i. calculating a difference between the value of the changed input before and after the change, and

ii. adding the difference to the or each problem expressions dependent thereon.

20. A computer program, or a suite of computer programs comprising a set of instructions to cause a computer, or a suite of computers, to carry out the method steps of claims 1 to 5.

6. A problem modelling tool for building a model of a problem that involves a plurality of variables,

whereby a heuristic search method can be carried out to optimise a solution for the modelled problem, and

wherein the model of a problem comprises a plurality of expressions defined as corresponding one or more declarative statements and at least some of the expressions are dependent on at least one of said variables, and the problem modelling tool includes means for automatically updating the or each declarative statement in response to changes to the or each variable associated therewith.

7. A problem modelling tool according to claim 6, wherein the, or each, declarative statement is defined using one of a plurality of operators.

8. A problem modelling tool according to claim 7, wherein the operators include Boolean, arithmetic, logical, string, object and set operators.

9. A problem modelling tool according to any one of claims 6 to 8, wherein the plurality of variables includes static parameters that are static during the heuristic search for optimising a solution to the problem.

10. A problem modelling tool according to any one of claims 6 to 9, wherein the plurality of variables includes dynamic parameters that are modified during the heuristic search for optimising a solution to the problem.

11. A problem modelling tool according to any one of claims 6 to 10, wherein each declarative statement used in the problem model may be so arranged that a declarative statement based on a first set of variables, representing a first candidate solution, may be modified in response to a second set of variables, corresponding to a second candidate solution, causing update of a second declarative statement.

12. A problem modelling tool according to any one of claims 6 to 11, further including a heuristic searching means arranged to perform a heuristic search through candidate solutions for the problem model, to search for an optimised solution to the modelled problem.

13. A problem modelling tool according to claim 12, wherein the heuristic searching means includes a plurality of different heuristic searching parts configured so that the heuristic searching algorithm can be constructed from a selected plurality of the heuristic searching parts.

14. A problem modelling tool according to claim 13, including means adapted to evaluate the candidate solutions in the heuristic search for optimising a solution to the problem.

15. A problem modelling tool according to any one of claims 6 to 14, including visualising means arranged to visualise changes in one or more selected declarative statements in response to changes to the or each variable associated therewith.

16. A problem modelling tool according to claim 15, wherein the visualising means is further arranged to receive input indicative of changes to some of the variables and to transmit said changes to the means for automatically updating the or each corresponding declarative statement.

17. A method of constructing a model of a problem that involves a plurality of variables, the problem being definable by predetermined conditions, constraints and objectives, the method comprising the step of:

defining a plurality of expressions as corresponding one or more declarative statements, wherein at least some of the expressions are dependent on at least one of said variables and describe at least in part the conditions, constraints and objectives of said problem.

18. A method according to claim 17, in which the, or each, declarative statement is defined using one of a plurality of operators.

19. A method of optimising a model of a problem constructed according to claim 17 or claim 18, including the step of constructing a heuristic searching algorithm from a plurality of heuristic searching parts and applying the constructed heuristic search algorithm to the constructed model in order to optimise a solution for the modelled problem.

21. A computer program, or a suite of computer programs comprising a set of instructions to cause a computer, or a suite of computers, to carry out the method steps of claims 17 to 19.