Search

Iterative combinatorial auctions are known to resolve bidder preference elicitation problems. However, winner determination is a known key bottleneck that has prevented widespread adoption of such auctions, and adding a time-bound to winner determination further complicates the mechanism. As a result, heuristic-based methods have enjoyed an increase in applicability. We add to the growing body of work in heuristic-based winner determination by proposing an ant colony metaheuristic–based anytime algorithm that produces optimal or near-optimal winner determination results within specified time. Our proposed algorithm resolves the speed versus accuracy problem and displays superior performance compared with 20 past state-of-the-art heuristics and two exact algorithms, for 94 open test auction instances that display a wide variety in bid-bundle composition. Furthermore, we contribute to the literature in two predominant ways: first, we represent the winner determination problem as one of finding the maximum weighted path on a directed cyclic graph; second, we improve upon existing ant colony heuristic–based exploration methods by implementing randomized pheromone updating and randomized graph pruning. Finally, to aid auction designers, we implement the anytime property of the algorithm, which allows auctioneers to stop the algorithm and return a valid solution to the winner determination problem even if it is interrupted before computation ends. Combinatorial auctions (CAs) are used to allocate bundles of items among interested bidders. However, to resolve bidder preference elicitation problems, CAs are conducted iteratively. Winner determination is a key bottleneck that restricted the widespread adoption of such iterative CAs. Time bounded winner determination is further complicated by the increased variety and velocity of bids each round, and so regular solvers such as IBM CPLEX and A Mathematical Programming Language have been demonstrably ineffective in determining winners within a short duration. In response, heuristic-based methods have enjoyed an increase in applicability. We add to the growing body of work in heuristic-based winner determination by proposing an ant colony–based anytime algorithm (traveling ants for combinatorial auctions, or TrACA) that produces optimal or near-optimal winner determination results within specified time. Experiments are performed on 94 open test instances that display a variety in bid-bundle composition. We show and compare the performance of TrACA to 20 most recent state-of-the-art heuristics and two of the best exact algorithms (CPLEX and Max W Clique). Compared with 12 of 20 heuristics that employ classic search (e.g., stochastic local search, tabu search) or genetic or memetic algorithms, TrACA does significantly better on all instances. On the other eight heuristics that employ advanced hybrid search methodologies (e.g., hyperheuristics, biased random keys), TrACA performs significantly better on the harder test instances. Additionally, we show that TrACA resolves the trade-off between time and accuracy by achieving optimal solutions on 76 out of 94 instances, in at most one-sixth the time taken by exact algorithms. Finally, we analyze the TrACA search process and highlight factors that make TrACA suitable for solving hard auction instances within a prespecified (short) duration. [ABSTRACT FROM AUTHOR]

A dynamic slicing algorithm is proposed in this paper along with its implementation which is dynamic for concurrent Component-oriented programs carrying multiple threads. As a part of representing the concurrent COP (CCOP) effectively, an intermediate graph is developed called Concurrent Component Dependency Graph (CCmDG). The system dependence graph (SDG) for individual components and interfaces are integrated to represent the above intermediate graph. It also consists of some new dependence edges which have been triggered for connecting the individual dependence graph of each component with the interface. Based on the graph created for the CCOP, a dynamic slicing algorithm is proposed, which sets the resultant by making the executed nodes marked during run time in Concurrent Components Dynamic Slicing (CCmDS) appropriately. For checking the competence of our algorithm, five case studies have been considered and also compared with an existing technique. From the study, we found that our algorithm results in smaller and precise size slice compared to the existing algorithm in less time. [ABSTRACT FROM AUTHOR]