Granted Patent B2

US 7,640,189 · App. 10/411,879 · Granted Dec 29, 2009

Abstract

Claims (109)

1. A computer-implemented method for determining winning bid(s) in a combinatorial auction or exchange comprising:

(a) storing bids in a memory of a computer, wherein each bid includes one or more items and a bid price associated with said one or more items;

(b) directing a processor of the computer to choose one of the received bids;

(c) directing the processor to select bids from the received bids as a function of the bid chosen in step (b), wherein the selected bids include the chosen bid;

(d) directing the processor to form in the memory from said selected bids at least part of a search tree that includes inclusion branches and exclusion branches and which defines for each selected bid at least one node on one level of the search tree that is connected to at least one other node on another level of the search tree by either an inclusion branch or an exclusion branch;

(e) directing the processor to search a plurality of unique paths of the search tree to determine for each path a candidate allocation of the selected bids, wherein each candidate allocation includes a combination of the selected bids that lie along the corresponding search path and a price that is the sum of the bid prices of the combination of the selected bids; and

(f) when the processor determines that a price of a candidate allocation is better than a current price of a best allocation stored in a memory location, updating the memory location storing the best allocation and its price with the candidate allocation and its price.

2. The method of claim 1 , wherein step (e) includes:

determining an upper bound price of a first group of bids of a subtree of the search tree;

determining a difference between (1) a sum of the price(s) of the bid(s) that lie on a search path connected to the subtree and (2) the current price of the best allocation;

if the upper bound price is less than or equal to said difference, excluding each branch of the subtree from the search path; and

if the upper bound price is greater than said difference, include at least one branch of the subtree on the search path.

3. The method of claim 2 , wherein determining the upper bound includes:

(1) forming a first linear program matrix for the first group of bids wherein each column of the first matrix represents one of bids of the first group of bids, the intersection of each row and each column includes a variable and a quantity of the corresponding item in the corresponding bid, and the sum of the quantities in each row equals the total quantity of the corresponding item available in a forward auction, the total quantity of the corresponding item required in a reverse auction or zero (0) in an exchange;

(2) defining an objective for the first matrix;

(3) relaxing each requirement that a solution of the first matrix cause at least one variable thereof to have an integer value whereupon the at least one variable can have any numeric value;

(4) solving the first matrix to achieve the objective thereby determining values for the variables; and

(5) determining the upper bound price of the first group of bids as a function of the thus determined values of the variables of the first matrix.

4. The method of claim 3 , wherein the objective is either maximize the cost of items sold in a forward auction, minimize the cost of items purchased in reverse auction or maximize a difference between the cost of items sold and the cost of items purchased in an exchange.

5. The method of claim 3 , further including, terminating the search if the at least one variable that would have an integer value had each requirement in step (3) not been relaxed has an integer value in response to the solution in step (4).

6. The method of claim 3 , further including:

identifying a second group of bids that is a subset of the first group of bids;

forming a second linear program matrix for the second group of bids wherein each column of the second matrix represents one of the bids of the second group of bids, the intersection of each row and each column includes a variable and a quantity of the corresponding item in the corresponding bid, and the sum of the quantities in each row equals the total quantity of the corresponding item available in a forward auction, the total quantity of the corresponding item required in a reverse auction or zero (0) in an exchange;

relaxing each requirement that a solution of the second matrix cause at least one variable thereof to have an integer value whereupon the at least one variable can have any numeric value;

assigning to the value of the variable at the intersection of each row and column of the second matrix the value determined for the variable at the intersection of the corresponding row and column of the first matrix; and

determining the upper bound price of the second group of bids as a function of the substituted values of the variables in the second matrix.

7. The method of claim 3 , wherein the solution of the first matrix in step (4) progresses until the upper bound price is greater than said difference.

8. The method of claim 1 , wherein, when a first selected bid has an item in common with a second selected bid, only the first selected bid or the second selected bid is included in a candidate allocation.

9. The method of claim 3 , wherein, when no selected bid has an item in common with another selected bid, all of the selected bids can be included in a candidate allocation.

10. The method of claim 3 , wherein, in step (b), the one received bid is chosen based on at least one of the following heuristics:

the bid having the highest normalized bid price;

the bid having a bid price with the highest surplus above the worth of the one or more items thereof;

the bid having the highest number of at least one item in common with another bid;

the bid having the largest number of items,

the bid whose variable has the value closest to 1; and

the bid whose variable has the value closest to 0.5.

11. The method of claim 10 , wherein the at least one heuristic to be applied depends on a characteristic of the linear program matrix.

12. The method of claim 11 , wherein said characteristic includes at least one of the following:

the number of columns in the first matrix;

the number of rows in the first matrix;

the number of nonzero coefficients in the first matrix; and

the number of nonzero coefficients in the first matrix divided by the product of the number of columns and the number of rows in the first matrix.

13. The method of claim 1 , further including:

separating the selected bids into at least one group of disjoint bids; and

determining an upper bound for each group of bids.

14. The method of claim 13 , further including:

(h) determining for one group of bids a value MIN that represent a minimum price the group of bids must exceed to find a candidate allocation that has a price better than the current price of the best allocation;

(i) if the upper bound for the group of bids is less than MIN for the group of bids, terminating searching the group of bids, otherwise defining from the group of bids a first subgroup of bids;

(j) choosing one of the bids of the first subgroup of bids;

(k) selecting bids from the first subgroup of bids as a function of the bid chosen in step (j), wherein the bids selected from the first subgroup of bids include the bid chosen in step (j);

(l) forming from the bids selected in step (k) at least part of another search tree that defines for each bid selected in step (k) at least one node on one level of the search tree that is connected to at least one other node on another level of the search tree by at least one of an inclusion branch and an exclusion branch;

(m) searching a plurality of unique paths of the other search tree to determine for each path a candidate allocation of the selected bids, wherein each candidate allocation includes a combination of the selected bids that lie along the corresponding search path and a price that is the sum of the bid prices of the combination of the selected bids; and

(n) when a price of a candidate allocation in step (m) is better than the current price of the best allocation, updating the best allocation and its price with the candidate allocation and its price.

15. A computer readable medium having stored thereon instructions which, when executed by a processor, cause the processor to perform the steps of:

(a) store bids in a memory of a computer, wherein each bid includes one or more items and a bid price associated with said one or more items;

(b) choose one of the received bids;

(c) select bids from the received bids as a function of the chosen bid, wherein the selected bids include the chosen bid;

(d) form in the memory from the selected bids at least part of a search tree that includes inclusion branches and exclusion branches and which defines for each selected bid at least one node on one level of the search tree that is connected to at least one other node on another level of the search tree by either an inclusion branch or an exclusion branch;

(e) search a plurality of unique paths of the search tree formed in the memory to determine for each path a candidate allocation of the selected bids, wherein each candidate allocation includes a combination of the selected bids that lie along the corresponding search path and a price that is the sum of the bid prices of the combination of the selected bids; and

(f) when a price of a candidate allocation is better than a current price of a best allocation stored in a memory location, update the memory location storing the best allocation and its price with the candidate allocation and its price.

16. The computer readable medium of claim 15 , wherein, in step (e), the instructions cause the processor to perform the steps of:

determine an upper bound price of a first group of bids of a subtree of the search tree;

determine a difference between (1) a sum of the price(s) of the bid(s) that lie on a search path connected to the subtree and (2) the current price of the best allocation;

if the upper bound price is less than or equal to said difference, exclude each branch of the subtree from the search path; and

if the upper bound price is greater than said difference, include at least one branch of the subtree on the search path.

17. The computer readable medium of claim 16 , wherein, when determining the upper bound, the instructions cause the processor to perform the steps of:

(1) form a first linear program matrix for the first group of bids wherein each column of the first matrix represents one of bids of the first group of bids, the intersection of each row and each column includes a variable, and a quantity of the corresponding item in the corresponding bid and the sum of the quantities in each row equals the total quantity of the corresponding item available in a forward auction, the total quantity of the corresponding item required in a reverse auction or zero (0) in an exchange;

(2) define an objective for the first matrix;

(3) relax each requirement that a solution of the first matrix cause at least one variable thereof to have an integer value whereupon the at least one variable can have any numeric value;

(4) solve the first matrix to achieve the objective thereby determining values for the variables; and

(5) determine the upper bound price of the first group of bids as a function of the thus determined values of the variables of the first matrix.

18. The computer readable medium of claim 17 , wherein the objective is either maximize the cost of items sold in a forward auction, minimize the cost of items purchased in reverse auction or maximize a difference between the cost of items sold and the cost of items purchased in an exchange.

19. The computer readable medium of claim 17 , wherein the instructions cause the processor to perform the further step of:

terminating the search if the at least one variable that would have an integer value had each requirement in step (3) not been relaxed has an integer value in response to the solution in step (4).

20. The computer readable medium of claim 17 , wherein the instructions cause the processor to perform the further steps of:

identify a second group of bids that is a subset of the first group of bids;

form a second linear program matrix for the second group of bids wherein each column of the second matrix represents one of the bids of the second group of bids, the intersection of each row and each column includes a variable and a quantity of the corresponding item in the corresponding bid and the sum of the quantities in each row equals the total quantity of the corresponding item available in a forward auction, the total quantity of the corresponding item required in a reverse auction or zero (0) in an exchange;

relax each requirement that a solution of the second matrix cause at least one variable thereof to have an integer value whereupon the at least one variable can have any numeric value;

assigning to the value of the variable at the intersection of each row and column of the second matrix the value determined for the variable at the intersection of the corresponding row and column of the first matrix; and

determine the upper bound price of the second group of bids as a function of the substituted values of the variables in the second matrix.

21. The computer readable medium of claim 17 , wherein the instructions cause the processor to perform the further step of:

terminate the solution of the first matrix in step (4) when the upper bound price is greater than said difference.

22. The computer readable medium of claim 15 , wherein, when a first selected bid has an item in common with a second selected bid, only the first selected bid or the second selected bid is included in a candidate allocation.

23. The computer readable medium of claim 19 , wherein, when no selected bid has an item in common with another selected bid, all of the selected bids can be included in a candidate allocation.

24. The computer readable medium of claim 17 , wherein, in step (b), the instructions cause the processor to perform the further step of:

choosing the one received bid based on at least one of the following heuristics:

the bid having the highest normalized bid price;

the bid having a bid price with the highest surplus above the worth of the one or more items thereof;

the bid having the highest number of at least one item in common with another bid;

the bid having the largest number of items,

the bid whose variable has the value closest to 1; and

the bid whose variable has the value closest to 0.5.

25. The computer readable medium of claim 24 , wherein the at least one heuristic to be applied depends on at least one characteristic of the linear program matrix.

26. The computer readable medium of claim 25 , wherein said at least one characteristic includes at least one of the following:

the number of columns in the first matrix;

the number of rows in the first matrix;

the number of nonzero coefficients in the first matrix; and

the number of nonzero coefficients in the first matrix divided by the product of the number of columns and the number of rows in the first matrix.

27. The computer readable medium of claim 15 , wherein the instructions cause the processor to perform the further steps of:

separate the selected bids into at least one group of disjoint bids; and

determine an upper bound for each group of bids.

28. The computer readable medium of claim 27 , wherein the instructions cause the processor to perform the further steps of:

(g) determine for one group of bids a value MIN that represent a minimum price the group of bids must exceed to find a candidate allocation that has a price better than the current price of the best allocation;

(h) if the upper bound for the group of bids is less than MIN for the group of bids terminate searching the group of bids, otherwise define from the group of bids a first subgroup of bids;

(i) choose one of the bids of the first subgroup of bids;

(j) select bids from the first subgroup of bids as a function of the bid chosen in step (i), wherein the bids selected from the first subgroup of bids include the bid chosen in step (i);

(k) form from the bids selected in step (j) at least part of another search tree that defines for each bid selected in step (j) at least one node on one level of the search tree that is connected to at least one other node on another level of the search tree by at least one of an inclusion branch and an exclusion branch;

(l) search a plurality of unique paths of the other search tree to determine for each path a candidate allocation of the selected bids, wherein each candidate allocation includes a combination of the selected bids that lie along the corresponding search path and a price that is the sum of the bid prices of the combination of the selected bids; and

(m) when a price of a candidate allocation in step (l) is better than the current price of the best allocation, update the best allocation and its price with the candidate allocation and its price.

Assignments (22)