Software tool for heuristic search methods

• US 7,406,475 B2
• Filed: 01/08/2002
• Issued: 07/29/2008
• Est. Priority Date: 01/09/2001
• Status: Expired due to Term

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Dorne, Raphael, Voudouris, Christos
• Primary Examiner(s): Le; Miranda
• Application Number:
  US10/250,950
• Publication Number:
  US 20040049479A1
• Time in Patent Office: 2,394 Days
• Field of Search: 707 1- 10, 707100-102, 707/104.1, 707200-201, 705 7- 9, 709/203, 709/224, 706/13
• US Class Current: N/A
• 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

A modeling tool for building a model of a problem involves a plurality of variables, whereby a heuristic search method can be carried out to optimize a solution for the modeled problem. The model of a problem includes a plurality of expressions defined as corresponding to one or more declarative statements and at least some of the expressions are dependent on at least one of the variables. The problem modeling tool can include automatically updating each declarative statement in response to changes to each variable associated therewith.

Claims

1. A method of optimizing 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 optimized in accordance with a predetermined optimization 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,

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

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

the method comprising:

(i) building a model of said resource allocation problem in accordance with said problem variables, problem expressions, problem constraints, and objective function, whereby a heuristic search method are carried out to optimize a solution for the modeled problem;

(ii) generating a solution to the modeled problem, the solution comprising a set of values representative of at least some of the problem variables;

(iii) generating a further solution to the modeled by;

(a) modifying one or more values in the set of variables representative of at least some of the problem variables for the previously generated solution;

(b) identifying problem expressions directly and indirectly dependent on the modified values and of the dependent problem expressions identified,

(c) selecting an identified problem expression from the dependent problem expressions identified at (b),

(d) evaluating whether one or more inputs to the selected problem expression has changed,

(e) 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, and, if the input has changed, evaluating the selected problem expression and evaluating all problem expressions directly and indirectly dependent on said selected problem expression,

(f) selecting the next problem expression identified at (b), and

(g) repeating (c)-(e) until there are no further problem expressions to be selected;

(iv) assessing whether the objective function satisfies the predetermined optimization criterion as a result of the change applied at (iii), and, if not, repeating (iii) until the objective function is deemed to satisfy the predetermined optimization criterion;

(v) determining whether the generated further solution better satisfies the objective function and if so, setting the generated further solution as the solution to be modified in (a);

(vi) repeating (iii) through (v) until a predetermined number of solutions have been generated; and

(vii) outputting the generated solution which best satisfies the objective function as a solution to the modeled problem.

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

3. A method according to claim 1, wherein evaluation of the selected problem expression comprises:

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

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

4. A problem modeling tool embodied in a computer-readable storage medium for optimizing 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 optimized in accordance with a predetermined optimization 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,

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

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

the problem modeling tool comprising:

(i) a modeler for building a model of said resource allocation problem in accordance with said problem variables, problem expressions, problem constraints, and objective function, whereby a heuristic search method are carried out to optimize a solution for the modeled problem;

(ii) a solver for generating a solution to the modeled problem, the solution comprising a set of values representative of at least some of the problem variables;

(iii) the solver being further operable to;

(a) modify one or more values in the set of variables representative of at least some of the problem variables for a previously generated solution;

(b) identify problem expressions directly and/or indirectly dependent on the modified values and of the dependent problem expressions identified,

(c) select an identified problem expression from the dependent problem expressions identified at (b),

(d) evaluate whether one or more inputs to the selected problem expression has changed,

(e) in a case where the or each input has not changed, mark the selected problem expression, and all problem expressions dependent on the said selected problem expression as unchanged, and if the input has changed, said solver evaluating the selected problem expression and evaluating all problem expressions directly and indirectly dependent on said selected problem expression,

(f) select the next problem expression identified at (b), and

(g) repeat (c)-(e) until there are no further problem expressions to be selected, in order to generate further solutions to the modeled problem;

(iv) said solver further assesses whether the objective function satisfies the predetermined optimization criterion as a result of the change applied at (iii), and, if not, repeating at (iii) until the objective function is deemed to satisfy the predetermined optimization criterion;

(v) a tester for determining whether each generated further solution better satisfies the objective function and if so, said tester being further operable to set the generated further solution as the solution to be modified in (a);

(vi) repeating (iii) through (v) until a predetermined number of solutions have been generated; and

(vii) a displayer for outputting the generated solution which best satisfies the objective function as a solution to the modeled problem.

5. A problem modeling tool embodied in a computer-readable storage medium according to claim 4, wherein evaluating whether an input to the selected problem expression has changed comprises recursively identifying and evaluating inputs to the input.

6. A problem modeling tool according to claim 4, wherein evaluation of the selected problem expression comprises:

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

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