Cost-optimizing allocation system and method

• US 6,272,483 B1
• Filed: 10/29/1998
• Issued: 08/07/2001
• Est. Priority Date: 10/31/1997
• Status: Expired due to Term

• Current Assignee: University of Oregon
• Original Assignee: University of Oregon
• Inventors: Joslin, David E., Clements, David P.
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/183,026
• Time in Patent Office: 1,013 Days
• Field of Search: 706/64, 705/7, 705/8
• US Class Current: 706/62
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

Abstract

A system for determining schedules and processing other optimization problems includes a local optimization engine and a global optimization engine. The local optimization engine operates based on heuristics, and includes a prioritizer, a constructor, and an analyzer to make large “coherent” moves in the search space, thus helping to avoid local optima without relying entirely on random moves. The global optimization engine takes the individual schedules produced by the local optimization engine and optimizes them using Linear Programming/Integer Programming techniques.

Claims

1. A method of generating cost-optimized solutions to an optimization problem, comprising the steps of:

receiving data representative of the optimization problem, the received data representative of a set of elements for assignment and a set of resources to which the elements can be assigned;

representing the elements in a prioritized list;

constructing an assignment of the elements in the prioritized list to the resources such that every resource is assigned a subset of elements in a highest-priority-first order, wherein the assignment forms a solution;

analyzing the solution to determine an excess cost for each element in the solution;

iterating the constructing and analyzing steps, and, with each iteration, elevating a priority of an element in the prioritized list by an amount determined responsive to the excess cost for that element to produce a plurality of solutions to the optimization problem; and

outputting data representative of the plurality of solutions to the optimization problem.

2. The method of claim 1, wherein the analyzing step comprises the steps of:

determining a minimum possible cost that each element can contribute to any solution;

determining an actual cost for each element based in part on the element'"'"'s position in the solution; and

determining the element'"'"'s excess cost from the element'"'"'s minimum possible cost and the element'"'"'s actual cost.

3. The method of claim 1, wherein the iterating step further comprising the steps of:

decomposing each of the plurality of solutions into a plurality of subsolutions.

4. The method of claim 3, further comprising the step of:

passing the plurality of subsolutions to a linear programming/integer programming (LP/IP) engine;

wherein each subsolution is a column in the LP/IP formulation of a set partitioning problem.

5. The method of claim 1, wherein the constructing step comprises the steps of:

representing the elements in a prioritized list; and

assigning the elements in the prioritized list to the resources in a highest-priority-first order.

6. The method of claim 5, further comprising the step of:

elevating a priority of an element by a distance that increases with a magnitude of an excess cost of the element.

7. The method of claim 1, wherein the constructing step comprises the step of:

greedily assigning elements to resources.

8. The method of claim 1, wherein computer instructions for performing the method steps are embodied on a computer-readable medium.

11. The computer-readable medium of claim 7, wherein the assigning step comprises the steps of:

representing the subset of elements in a prioritized list; and

assigning the elements in the prioritized list to the resources in a highest-priority-first order.

15. The computer-readable medium of claim 11, wherein the assigning step comprises the step of:

elevating a priority of an element in the prioritized list responsive to a magnitude of an identified excess cost of the element.

9. A computer-readable medium having computer program instructions embodied thereon for directing a computer to perform steps for generating cost-optimized solutions to an optimization problem, the steps comprising:

receiving data representative of the optimization problem, the received data representative of a set of elements for assignment and a set of resources to which elements can be assigned;

representing the elements in a prioritized list;

constructing an assignment of the elements in the prioritized list to the resources in a highest-priority-first order such that every resource is assigned a subset of elements, wherein the assignment forms a solution;

analyzing the solution to determine an excess cost for each element in the solution;

iterating the constructing and analyzing steps to produce a plurality of solutions to the optimization problem;

with each iteration, elevating a priority of an element in the prioritized list by an amount determined responsive to the excess cost for that element; and

outputting data representative of the plurality of solutions to the optimization problem.

10. The computer-readable medium of claim 9, further comprising the step of:

decomposing the solution generated by the constructing step into a plurality of subsolutions, wherein each subsolution includes a subset of elements and a subset of resources;

wherein the assigning and analyzing steps operate on the plurality of subsolutions to generate a plurality of solutions for each subsolution.

12. The computer-readable medium of claim 9, wherein the analyzing step comprises the step of:

determining a minimum possible cost that an element can contribute to any solution.

13. The computer-readable medium of claim 12, wherein the analyzing step further comprises the step of:

determining an actual cost for the element based in part on the element'"'"'s position in the solution.

14. The computer-readable medium of claim 13, wherein the analyzing step further comprises the step of:

determining the element'"'"'s excess cost from the element'"'"'s actual cost and the element'"'"'s minimum possible cost.

16. The computer-readable medium of claim 9, further comprising the steps of:

decomposing the data representative of the plurality of solutions into data representative of a plurality of subsolutions; and

processing the data representative of the plurality of subsolutions using linear programming/integer programming (LP/IP) techniques;

wherein the LP/IP techniques produce a plurality of new solutions.

17. A system for iteratively generating cost-optimized solutions to an optimization problem, comprising:

a storage device for storing data representative of the optimization problem and including a set of elements for assignment and a set of resources to which the elements can be assigned;

a prioritizer for storing the elements in a prioritized list and for elevating the priority of an element responsive to a penalty assigned to the element;

a constructor for assigning the elements in the prioritized list, in order of priority, to the resources, wherein a subset of elements is assigned to each resource and the assignments form a solution, and wherein iterations of the system produce a plurality of solutions;

an analyzer for assigning the penalty to each element in the solution and providing the penalties to the prioritizer, wherein the penalty is determincd responsive to an excess cost for the element; and

an output interface for outputting the plurality of solutions to the optimization problem.

18. The system of claim 17, wherein the prioritizer comprises:

a module for assigning random initial priorities to the elements in the prioritized list.

19. The system of claim 17, wherein the prioritizer comprises:

a module for applying a heuristic to assign initial priorities to the elements in the prioritized list.

20. The system of claim 17, wherein the analyzer comprises:

a module for determining a minimum possible penalty that an element can contribute to any solution.

21. The system of claim 20, wherein the analyzer further comprises:

a module for determining an element'"'"'s excess cost from the element'"'"'s actual penalty and the element'"'"'s minimum possible penalty.

22. The system of claim 17 further comprising:

a module for decomposing each of the plurality of solutions output by the output interface into a plurality of subsolutions; and

a linear programming/integer programming engine for treating each subsolution in the plurality of solutions as a column in a set partitioning problem.

23. The system of claim 17, wherein the prioritizer ranks the elements in the prioritized list in descending order of assigned penalties.

24. The system of claim 17, wherein particular elements are not included in the solution and the analyzer further comprises:

a module for assigning a penalty to each element not included in the solution, wherein the penalties assigned to elements not included in the solution are higher than the penalties assigned to elements in the solution.