Method of selecting one or more bids in a combinatorial auction

• US 7,010,505 B2
• Filed: 07/30/2001
• Issued: 03/07/2006
• Est. Priority Date: 07/28/2000
• Status: Expired due to Term

• Current Assignee: SciQuest Incorporated
• Original Assignee: Combinenet Incorporated (Jaggaer LLC)
• Inventors: Hoos, Holger H., Boutilier, Craig E.
• Primary Examiner(s): Smith, Jeffrey A.
• Application Number:
  US09/918,164
• Publication Number:
  US 20020052829A1
• Time in Patent Office: 1,681 Days
• Field of Search: 705/26, 705/27, 705/37
• US Class Current: 705/26.3
• CPC Class Codes: G06Q 30/08 Auctions
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange

Abstract

A method of selecting a winning allocation of bids in a combinatorial auction includes receiving a plurality of bids and designating a subset of the received bids as a current allocation having no overlap in the items of its bids. For each bid not part of the current allocation, a neighboring allocation is determined by combining the bid with the current allocation and deleting from such combination any bid of the current allocation having an item that overlaps an item of the bid combined with the current allocation. A heuristic is determined for each neighboring allocation and one of the neighboring allocations is selected stochastically or based on its heuristic. If this one neighboring allocation is greater than the value of the best allocation, the current allocation is substituted for the best allocation.

Claims

1. A method of selecting one or more winning bids in a combinatorial auction comprising the steps of:

(a) receiving a plurality of bids each comprising one or more items and an associated value for the one or more items;

(b) designating a subset of the bids as a current allocation, wherein, when the current allocation includes two or more bids, each bid of the current allocation has no item in common with another bid of the current allocation;

(c) determining a plurality of neighboring allocations, each neighboring allocation comprising a combination of the current allocation and a new bid selected from the bids not part of the current allocation or any other neighboring allocation, each neighboring allocation excluding each bid that has at least one item in common with the new bid;

(d) replacing the current allocation with one of the neighboring allocations, where a computer selects the one neighboring allocation from the plurality of neighboring allocations stochastically or based on a heuristic value determined for the one neighboring allocation;

(e) updating a best allocation with the current allocation if a sum of the values of the bids of the current allocation is greater than or equal to a sum of the values of the bids of the best allocation; and

(f) repeating steps (c)–

(e) M times, wherein in step (d) the one neighboring allocation is selected stochastically a first part of M times and is selected based on the heuristic value a second part of M times.

2. The method as set forth in claim 1, wherein, in step (d), the selection of the one neighboring allocation stochastically or based on a heuristic value is based on a probability function or a random number generating algorithm.

3. The method as set forth in claim 1, further including the step of initializing at least one of the best allocation and the sum of the values of the bids of the best allocation.

4. The method as set forth in claim 1, further including the step of determining a heuristic value for each neighboring allocation, where each heuristic value is an indication of a capacity of its neighboring allocation to increase a sum of the values of the current allocation.

5. The method as set forth in claim 4, wherein the selection of each of the one neighboring allocations is based on the heuristic value therefor indicating that the one neighboring allocation maximizes an increase in the sum of the values of the current allocation over any increase that would be generated by any other neighboring allocation.

6. The method as set forth in claim 4, wherein determining the heuristic value for each neighboring allocation includes the steps of:

determining a difference in a sum of the values of the bids of the neighboring allocation and the sum of the values of the bids of the current allocation; and

dividing the difference in the sum of the values by the total number of items of the bids comprising the neighboring allocation.

7. The method as set forth in claim 6, wherein the difference in the sum of the values is one of a negative difference, a positive difference and zero.

8. The method as set forth in claim 4, wherein step (d) includes the steps of:

identifying a first neighboring allocation having a first heuristic value that has a first predetermined relation to the heuristic values of the other neighboring allocations;

identifying a second neighboring allocation having a second heuristic value that has a second predetermined relation to the heuristic values of the other neighboring allocations;

determining a first age of a first new bid combined with the current allocation to form the first neighboring allocation, the first age based on the number of times at least one of steps (c)–

(d) is repeated since the first new bid comprised a neighboring allocation that replaced a previous current allocation;

determining a second age of a second new bid combined with the current allocation to form the second neighboring allocation, the second age based on the number of times at least one of steps (c)–

(d) is repeated since the second new bid comprised a neighboring allocation that replaced a previous current allocation;

if the first age is greater than the second age, replacing the current allocation with the first neighboring allocation; and

if the second age is greater than the first age, stochastically replacing the current allocation with the second neighboring allocation a first part of X times and replacing the current allocation with the first neighboring allocation a second part of X times.

9. The method as set forth in claim 8, wherein the first heuristic value is the largest heuristic value and the second heuristic value has a value second largest only to the first heuristic value.

10. The method as set forth in claim 9, wherein the largest heuristic value is large in a positive sense.

11. The method as set forth in claim 8, wherein X times is less than M times.

12. The method as set forth in claim 1, further including the step of repeating steps (b)–

(f) N times, wherein, each time step (b) is repeated, the subset of the bids designated as the current allocation is selected stochastically.

13. A method of selecting a winning allocation of bids in a combinatorial auction comprising the steps of:

(a) receiving a plurality of bids each comprising one or more items and a value;

(b) designating a subset of the bids as a current allocation, the current allocation having no overlap in the items of its bids;

(c) determining a neighboring allocation for each bid not part of the current allocation by combining the bid with the current allocation and deleting from such combination any bid associated with the current allocation having an item that overlaps an item of the bid combined with the current allocation;

(d) determining for each neighboring allocation a heuristic indicative of a capacity of the neighboring allocation to increase a sum of the values of the bids of the current allocation;

(e) causing a computer to select one of the neighboring allocations stochastically a part of M times or based on the heuristics determined in step (d) the remainder of M times;

(f) replacing the current allocation with the selected one of the neighboring allocations;

(g) if the sum of the values of the bids of the current allocation is greater than or equal to a sum of the values of the bids of a best allocation, substituting the current allocation for the best allocation; and

(h) repeating steps (c)–

(g) M times.

14. The method as set forth in claim 13, further including the step of repeating steps (b)–

(h) N times, wherein for each repetition of step (b) the subset of the bids of the current allocation is selected stochastically.

15. The method as set forth in claim 13, wherein a probability function or a random number generating algorithm is utilized to select each one of the neighboring allocations stochastically or based on the heuristics in step (e).

16. The method as set forth in claim 13, wherein step (d) includes the steps of:

identifying a first heuristic having a value indicative of its neighboring allocation having the capacity to produce a change in the sum of the values of the bids of the current allocation greater than any other neighboring allocation;

identifying a second heuristic having a value indicative of its neighboring allocation having the capacity to produce a change in the sum of the values of the bids of the current allocation second only to the neighboring allocation associated with the first heuristic;

determining a first age of the bid combined with the current allocation to form the neighboring allocation associated with the first heuristic, the first age determined from the number of steps performed since the bid associated with the first heuristic comprised a neighboring allocation that replaced a previous current allocation;

determining a second age of the bid combined with the current allocation to form the neighboring allocation associated with the second heuristic, the second age determined from the number of steps performed since the bid associated with the second heuristic comprised a neighboring allocation that replaced a previous current allocation;

if the first age is greater than the second age, replacing the current allocation with the neighboring allocation associated with the first heuristic; and

if the second age is greater than the first age, stochastically replacing the current allocation with the neighboring allocation associated with the second heuristic a first part of X times and replacing the current allocation with the neighboring allocation associated with the first heuristic a second part of X times.

17. The method as set forth in claim 16, wherein a probability function or a random number generating algorithm is utilized to determine whether the current allocation is replaced with the neighboring allocation associated with the second heuristic or the current allocation is replaced with the neighboring allocation associated with the first heuristic.

18. A method of selecting one or more bids in a combinatorial auction comprising the steps of:

(a) receiving a plurality of bids each comprising one or more items and a value;

(b) designating a subset of the bids as a current allocation;

(c) combining each bid not part of the current allocation with the current allocation to form a corresponding neighboring allocation for each bid;

(d) causing a computer to select one of the neighboring allocations stochastically or based on a heuristic determined for the selected neighboring allocation, said heuristic indicative of a capacity of the selected neighboring allocation to affect a sum of the values of the bids of the current allocation;

(e) replacing the current allocation with the selected neighboring allocation; and

(f) repeating steps (c)–

(e) M times, with the selected neighboring allocation being selected stochastically a first part of M times and with the selected neighboring allocation being selected based on the heuristic a second part of M times.

19. The method as set forth in claim 18, further including the step of deleting from at least the selected neighboring allocation any bid having an item that overlaps an item of the bid combined with the current allocation to form the selected neighboring allocation.

20. The method as set forth in claim 18, wherein step (d) includes utilizing simulated annealing, tabu/taboo search or iterative local search to select the one neighboring allocation.