Method of selecting one or more bids in a combinatorial auction

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.

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.