Cost-optimizing allocation system and method
AssigneeThe State of Oregon Acting by and through the State Board of Higher Education on Behalf of the University of Oregon
InventorsDavid E. Joslin, David P. Clements
Life of this patent
Estimating the term…
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.
Claims24
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.
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.
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.
Dependencies are inferred from the claim text.