| Combinatorial Auctions (CA) serve a role in practical problems such as assigning shipping routes, airport landing slots, and even advertising. The problem of awarding bids in these auctions, the winner determination problem (WDP), is well known to be NP-complete, as are many of the bid generation problems that must be solved by participants. Therefore, while much research has been concentrated on finding optimal solutions for these problems, many variants are real-time problems and require faster solutions than can be obtained from exact methods. Our paper implements a heuristic which falls into the class of Stochastic Local Search (SLS) to solve the general CA problem. The solutions are found quickly even on larger data sets. The downside to SLS is that the solutions are not guaranteed to be optimal; however they are consistently better than greedy algorithms and appear to be quite good. |
