System for optimizing a network plan and method of operation

• US 5,943,244 A
• Filed: 02/17/1997
• Issued: 08/24/1999
• Est. Priority Date: 02/17/1997
• Status: Expired due to Term

• Current Assignee: JDA Software Group Incorporated (RedPrairie Holding Incorporated)
• Original Assignee: i2 Technologies Incorporated (Panasonic Holdings Corporation)
• Inventors: Hogge, John C., Crawford, James M. Jr., Kennedy, Brian M.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Roberts, A. S.
• Application Number:
  US08/800,717
• Time in Patent Office: 918 Days
• Field of Search: 364/512, 364/578, 364/148, 395/500
• US Class Current: 703/13
• 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

Abstract

A system is provided for optimizing a network plan. The system includes a memory which stores information specifying a network plan, a plurality of constraints, and a plurality of interaction coefficients. Each interaction coefficient corresponds to particular constraint. A processor is coupled to the memory. The processor is operable to determine whether the network plan violates any of the constraints, modify the network plan in order to resolve a violation of any constraint, and update a corresponding interaction coefficient in order to reflect an impact upon the network plan caused by the resolution of a violation.

Claims

1. A computer-implemented system for solving a network planning problem, the system comprising:

a memory operable to store information specifying a network plan, a plurality of constraints, and a plurality of interaction coefficients, each interaction coefficient corresponding to particular constraint, and at least one goal; and

a processor coupled to the memory, the processor operable to model said network, said constraints, and said at least one goal as a constraint satisfaction problem, to initialize said interaction coefficients for each solution to said problem, and to provide said solution by iteratively repeating the following steps;

to determine whether a proposed network plan violates any of the constraints, if so, to update an interaction coefficient corresponding to each violated constraint, said coefficient reflecting an impact upon said at least one goal caused by the resolution of a violation, to select a constraint violation to be resolved on the basis of said interaction coefficient, and to generate a new plan in accordance with resolution of a selected constraint violation;

said processor further operable to provide data representing a display pertaining to said solution.

2. The system of claim 1, wherein the constraints are separated into at least one grouping, the processor further operable to update the corresponding interaction coefficients for each constraint within the grouping in order to reflect an impact upon the network plan caused by the resolution of a violation of one constraint in the grouping.

3. The system of claim 2, wherein the network plan is provided for a network comprising a plurality of interacting elements, and wherein the constraints are grouped according to association with a particular element of the network.

4. The system of claim 2, wherein the constraints are grouped according to association with a particular type of problem.

5. The system of claim 2, wherein each constraint has a corresponding size, and wherein the constraints are grouped according to size.

6. The system of claim 1, wherein the memory is operable to store information specifying a goal weight, a size for a violation of a constraint, a catchall value.

7. The system of claim 6, wherein the processor is operable to update an interaction coefficient using the goal weight, the size for a violation of a constraint, and the catchall value.

8. The system of claim 1, wherein the processor is further operable to modify the network plan using the updated interaction coefficient.

9. A computer-implemented system for solving a network planning problem, the system comprising:

a memory operable to store information specifying a network plan, a plurality of constraints, and a plurality of interaction coefficients, each interaction coefficient corresponding to particular constraint, and at least one goal;

a constraint checker module operable to access the memory, the constraint checker module operable to determine whether the network plan violates any of the constraints; and

a resolver module operable to communicate with the constraint checker module, the resolver module operable to initialize said intereaction coefficients for each solution to said problem, and to provide said solution by iteratively repeating the following steps;

to update an interaction coefficient corresponding to each violated constraint, said coefficient reflecting an impact upon the at least one goal caused by the resolution of a violation, to select a constraint violation to be resolved on the basis of said interaction coefficient, to generate a new plan in accordance with resolution of a selected constraint violation;

a network plan memory operable to provide data representing a display pertaining to said solution.

10. The system of claim 9, further comprising a solver module operable to communicate with the constraint checker module, the solver module operable to invoke the resolver module if it is determined that the network plan violates any of the constraints.

11. The system of claim 9, wherein the constraints are separated into at least one grouping, the constraint checker module further operable to update the corresponding interaction coefficients for each constraint within the grouping in order to reflect an impact upon the network plan caused by the resolution of a violation of one constraint in the grouping.

12. The system of claim 11, wherein the network plan is provided for a network comprising a plurality of interacting elements, and wherein the constraints are grouped according to association with a particular element of the network.

13. The system of claim 11, wherein the constraints are grouped according to association with a particular type of problem.

14. The system of claim 11, wherein each constraint has a corresponding size, and wherein the constraints are grouped according to size.

15. A computer-implemented method for solving a network planning problem, the method comprising the steps of:

receiving information specifying a network plan, a plurality of constraints, and a plurality of interaction coefficients, each interaction coefficient corresponding to particular constraint and at least one goal;

determining whether the network plan violates any of the constraints;

if one or more constraints is violated, to initialize said interaction coefficients for each solution to said problem, and to provide said solution by iteratively repeating the following steps;

updating an interaction coefficient corresponding to each violated constraint, said coefficient reflecting an impact upon the at least one goal caused by the resolution of a violation, selecting a constraint violation to be resolved on the basis of said interaction coefficient, and generating a new plan in accordance with resolution of a selected constraint violation; and

providing data representing a display pertaining to said solution.

16. The method of claim 15, further comprising the step of modifying the network plan using the updated interaction coefficient.

17. The method of claim 15, wherein the constraints are separated into at least one grouping, and further comprising the step of updating the corresponding interaction coefficients for each constraint within the grouping in order to reflect an impact upon the network plan caused by the resolution of a violation of one constraint in the grouping.

18. The method of claim 17, wherein the network plan is provided for a network comprising a plurality of interacting elements, and wherein the constraints are grouped according to association with a particular element of the network.

19. The method of Claim 17, wherein the constraints are grouped according to association with a particular type of problem.

20. The method of claim 17, wherein each constraint has a corresponding size, and wherein the constraints are grouped according to size.