Combinatorial auction branch on bid searching method and apparatus

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

• (a) receive bids, 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 from the selected bids at least part of a search tree that 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 at least one of an inclusion branch and an exclusion branch;
• (e) 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 a price of a candidate allocation is better than a current price of a best allocation, update the best allocation and its price with the candidate allocation and its price.