System and method for optimizing the allocation of a resource

• US 6,321,207 B1
• Filed: 04/15/1999
• Issued: 11/20/2001
• Est. Priority Date: 04/15/1999
• Status: Expired due to Term

• Current Assignee: JDA Software Group Incorporated (Panasonic Holdings Corporation)
• Original Assignee: i2 Technologies US Incorporated (Panasonic Holdings Corporation)
• Inventors: Ye, Jian
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): NORMAN, MARC E
• Application Number:
  US09/292,644
• Time in Patent Office: 950 Days
• Field of Search: 705/7, 705/8, 705/9, 705/28
• US Class Current: 705/7.25
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/06315 Needs-based resource requirements planning or analysis

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.

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.

2. The system of claim 1, wherein the resource is at least one shipping lane, the bids are carrier bids, and the solution optimizes the allocation of the lane among a plurality of carriers.

3. The system of claim 1, wherein the engine is operable to identify bids that span the resource and to determine a cutoff unit price for the resource, the engine operable to compare the unit prices of the bids that span the resource with the cutoff unit price in generating the priorities.

4. The system of claim 1, wherein the engine is operable to identify bids that span the resource and to order the bids according to their unit prices, the engine operable to select the bids with the lowest unit prices until the sum of bid amounts for the selected bids exceed a threshold, the unit price of the last selected bid being a cutoff unit price, the engine operable to compare the unit prices of the bids that span the resource with the cutoff unit price to generate priority values for the bids that span the resource.

5. The system of claim 4, wherein the threshold comprises a cutoff factor times the demand.

6. The system of claim 4, wherein the engine is operable to determine the priority of a particular bid according to the sum of its priority values across a plurality of resources.

7. The system of claim 1, wherein the engine is operable to adjust the priority of a bid according to a fixed cost associated with a submitter of the bid.

8. The system of claim 1, wherein the data further comprises a fixed cost F associated with a submitter of at least some of the bids, the engine operable to identify n bids of a submitter having positive priorities and to subtract F/n from the priorities of these bids to adjust the priorities of these bids.

9. The system of claim 1, wherein the engine is operable to assign a branch direction to a bid according to its priority.

10. The system of claim 1, wherein the priorities collectively specify an order in which the solver branches on variables corresponding to bids.

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.

12. The engine of claim 11, wherein the resource is at least one shipping lane, the bids are carrier bids, and the solution optimizes the allocation of the lane among a plurality of carriers.

13. The engine of claim 11, wherein the engine is operable to identify bids that span the resource and determine a cutoff unit price for the resource, the engine operable to compare the unit prices of the bids that span the resource with the cutoff unit price in generating the priorities.

14. The engine of claim 11, wherein the engine is operable to identify bids that span the resource and to order the bids according to their unit prices, the engine operable to select the bids with the lowest unit prices until the sum of bid amounts for the selected bids exceed a threshold, the unit price of the last selected bid being a cutoff unit price, the engine operable to compare the unit prices of the bids that span the resource with the cutoff unit price to generate priority values for the bids that span the resource.

15. The engine of claim 14, wherein the threshold comprises a cutoff factor times the demand.

16. The engine of claim 14, wherein the engine is operable to generate the priority of a particular bid according to the sum of its priority values across a plurality of resources.

17. The engine of claim 11, wherein the engine is operable to adjust the priority of a bid according to a fixed cost associated with a submitter of the bid.

18. The engine of claim 11, wherein the data further comprises a fixed cost F associated with a submitter of at least some of the bids, the engine operable to identify n bids of a submitter having positive priorities and to subtract F/n from the priorities of these bids to adjust the priorities of these bids.

19. The engine of claim 11, wherein the engine is operable to assign a branch direction to a bid according to its priority.

20. The engine of claim 11, wherein the priorities collectively specify an order in which the solver is to branch on variables corresponding to bids.

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.

22. The process of claim 21, wherein the resource is at least one shipping lane, the bids are carrier bids, and the solution optimizes the allocation of the lane among a plurality of carriers.

23. The process of claim 21, further comprising:

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.