Seminars & Colloquia
Electrical Engineering Dept. , Univ. of Ljubljana, Slovenia
"On the Scalability and the Performance Optimization
of Combinatorial Auction Solvers Using Isomorphs"
Tuesday September 05, 2006 04:30 PM
Location: Room 406, Daniels Hall NCSU Historical Campus
(Visitor parking instructions)
-- '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
(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'
Host: Negash Medhin, Operations Research, NCSU