Patent ID: 7702561

Claim:
A computer implemented method for identifying a cost-minimizing bid set for a reverse combinatorial auction where all-of-nothing-bids are allowed, the computer performing the steps of: receiving in a computer a plurality of bids, each bid having a timestamp, a bid price and item information identifying at least one bid item; introducing in the computer a decision variable for each bid; introducing in the computer a counting variable to indicate whether bids from a supplier are chosen in an optimal bid set; modeling demand constraints by the computer for each item using decision variable for each bid; modeling minimum and maximum numbers of suppliers by the computer based on the counting variables; introducing in the computer dummy bids, based on said modeled demand constraints, to ensure computability of a cost-minimizing bid set meeting said modeled demand constraints; providing the computer with an objective of choosing bids that arrive early, for a given cost, based on an additional timestamped objective with the given cost level as a constraint; introducing price modifications in the computer to at least one of said bid's respective item information and adjusting, based on said price modifications, the provided objective of choosing bids that arrive early, and generating a winner of the reverse combinatorial auction by the computer, by selecting the cost-minimizing bid set from among said plurality of bids, the selecting based on said time stamps, said bid prices, said item information, said provided objective of choosing bids that arrive early, and said modeled demand constraints.