System and method for optimizing the allocation of a resource
First Claim
1. A computer-based system for optimizing the allocation of a resource, comprising:
- an optimizer file containing resource allocation data comprising a demand and a plurality of bids for the resource, each bid comprising at least a unit price for the resource;
an optimizer engine coupled to the file and operable to receive the data, the engine operable to generate priorities for at least some bids according to their unit prices, the engine operable to generate an integer program according to the data and to communicate the priorities in association with the integer program; and
a solver coupled to the engine and operable to receive the priorities and integer program, the solver operable to generate a solution to the integer program using the priorities, the solution optimizing the allocation of the resource subject to the demand and the bids;
the solver branching, within a branch-and-bound tree data structure, on at least one variable corresponding to at least one bid according to the priority of the bid.
15 Assignments
0 Petitions
Accused Products
Abstract
A system (8) for optimizing the allocation of a resource includes an optimizer file (14) containing resource allocation data including a demand and multiple bids for the resource, each bid including at least a unit price for the resource. An optimizer engine (16) coupled to the file (14) receives the data and generates priorities for at least some of the bids according to their unit prices. The engine (16) generates an integer program according to the data and communicates the priorities in association with the integer program. A solver (18) coupled to the engine (16) receives the priorities and the integer program. The solver (18) generates a solution to the integer program using the priorities, the solution optimizing the allocation of the resource subject to the demand and the bids.
-
Citations
30 Claims
-
1. A computer-based system for optimizing the allocation of a resource, comprising:
-
an optimizer file containing resource allocation data comprising a demand and a plurality of bids for the resource, each bid comprising at least a unit price for the resource;
an optimizer engine coupled to the file and operable to receive the data, the engine operable to generate priorities for at least some bids according to their unit prices, the engine operable to generate an integer program according to the data and to communicate the priorities in association with the integer program; and
a solver coupled to the engine and operable to receive the priorities and integer program, the solver operable to generate a solution to the integer program using the priorities, the solution optimizing the allocation of the resource subject to the demand and the bids;
the solver branching, within a branch-and-bound tree data structure, on at least one variable corresponding to at least one bid according to the priority of the bid. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. An optimizer engine operating on at least one computer for optimizing the allocation of a resource, wherein:
-
the engine is operable to receive resource allocation data comprising a demand and a plurality of bids for the resource, each bid comprising at least a unit price for the resource;
the engine is operable to generate priorities for at least some bids according to their unit prices;
the engine is operable to generate an integer program according to the data; and
the engine is operable to communicate the priorities in association with the integer program to a solver for generation of a solution to the integer program using the priorities, the solution optimizing the allocation of the resource subject to the demand and the bids;
the priorities allowing the solver to branch, within a branch-and-bound tree data structure, on at least one variable corresponding to at least one bid according to the priority of the bid. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A process operating on a computer for optimizing the allocation of a resource, comprising:
-
receiving resource allocation data comprising a demand and a plurality of bids for the resource, each bid comprising at least a unit price for the resource;
generating priorities for at least some bids according to their unit prices;
generating an integer program according to the data;
associating the priorities with the integer program; and
generating a solution to the integer program using the priorities, the solution optimizing the allocation of the resource subject to the demand and the bids;
generating the solution comprising branching, within a branch-and-bound tree data structure, on at least one variable corresponding to at least one bid according to the priority of the bid. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28, 29, 30)
identifying bids that span the resource;
determining a cutoff unit price for the resource; and
comparing the unit prices of the bids that span the resource with the cutoff unit price in generating the priorities.
-
-
24. The process of claim 21, further comprising:
-
identifying bids that span the resource;
ordering the bids according to their unit prices;
selecting the bids with the lowest unit prices until the sum of bid amounts for the selected bids exceed a threshold;
determining a cutoff unit price equal to the unit price of the last selected bid;
comparing the unit prices of the bids that span the resource with the cutoff unit price; and
generating priority values for the bids that span the resource according to the comparison.
-
-
25. The process of claim 24, wherein the threshold comprises a cutoff factor times the demand.
-
26. The process of claim 24, wherein the priority of a particular bid is determined according to the sum of its priority values across a plurality of resources.
-
27. The process of claim 21, further comprising adjusting the priority of a bid according to a fixed cost associated with a submitter of the bid.
-
28. The process of claim 21, wherein the data further comprises a fixed cost F associated with a submitter of at least some of the bids, further comprising:
-
identifying n bids of a submitter having positive priorities; and
subtracting F/n from the priorities of these bids to adjust the priorities of these bids.
-
-
29. The process of claim 21, further comprising assigning a branch direction to a bid according to its priority.
-
30. The process of claim 21, wherein the priorities collectively specify an order in which variables corresponding to bids are branched upon.
Specification