Abstract: Traditionally, the combinatorial auction problem (CAP) has been formulated as an integer programming problem that can be solved, in principle, by a 0-1 linear programming package such as 'cplex'. However, alternative packages make claims to scale better as the problem size increase, these include:

-- 'CABOB', a branch-and-bound heuristics (Sandholm et al)
-- 'SAG2', a simulated annealing with hybrid local moves (Guo et al)

Our approach explores the variability of lower bounds that are generated by a greedy heuristics known as 'opportunity cost algorithm' which is linear in terms of the bid graph (Akcoglu at al). The performance of this algorithm is strongly sensitive to the order in which the nodes are processed -- and an order always exists for which the bound represents a global maximum. Since the opportunity cost algorithm runs much faster than either branch-and-bound or simulated annealing heuristics, we embed this algorithm as the inner-most loop of an 'any time algorithm' and run it with a time budget that is comparable to the timeout of a package such cplex, also available on the same computing platform.

In this talk we outline a strategy for empirical performance evaluation of three solvers, each instrumented as an anytime solver: cplex, opcost, and mis101. Benchmarks come from various sources and we enhance them in two ways: (1) for each reference instance we generate a set of isomorphs by randomly relabeling instance variable names, and (2) for reference instances with at least one optimum known solution, we construct new instances of increasing size, each with a hidden optimum solution. The introduction of isomorphs significantly increases the robustness of each performance evaluation, the progression of related benchmarks of size n, 2n, 4n, ... is essential to assessing the scalability of each solver. Current results show suprises as well as promises for special purpose solvers such as opcost.

This work represents a joint research with Dr. Franc Brglez and Dr. Matt Stallmann.
----------------------
(Sandholm et al) CABOB: A Fast Optimal Algorithm for Winner Determination in Combinatorial Auctions, 'Management Science, 2005'
(Guo et al) Heuristics for a Bidding Problem, 'Computers and Operations Research 33, Elsevier Ltd., 2006'
(Akcoglu et al) Opportunity Cost Algorithms for Combinatorial Auctions, 'Kluwer Academic, 2002'

Short Bio: Dr. Andrej Kosir majored in mathematics and statistics at the University of Ljubljana. His PhD thesis was in the area of pattern recognition using invariant maps. He is now an Assistant Professor with the Department of Electrical Engineering at the University of Ljubljana. His research includes visual information content analysis, optimization methods, and statistical data analysis. Presently, he is visiting with the Computer Science Department at NCSU.