Mark Gritter (markgritter) wrote,
Mark Gritter

glpsol, again

It's been a while since I played with GLPK, but I was curious how well it does at combinatorial-auction problems (expressed as a integer-linear program) so I ran some experiments last night.

I created a short program to generate random bids:
* 51 different types of good, with one "special" good common to all bids
* each bidder values 5 randomly selected combinations of 3 to 6 items
* each bidder submits an XOR bid for all 5 combinations, for 3 randomly selected combinations, and for the top-valued combination

For the available inventory (the content of the auction) I used an average of 7 items of each good type, per bidder. This is low enough that many bids probably cannot be satisfied.

100 bidders: < 0.1 second (3817 non-zero coefficients)
1000 bidders: 0.3 seconds (41676 non-zero coefficients)
3000 bidders: 1.7 seconds (124828 non-zero coefficients)
10000 bidders: 52.1 seconds (415921 non-zero coefficients)

However, in these tests the integer solutions were close (or even identical) to the solutions of the relaxed (real-valued) linear program, so the solver did not have to work very hard. This is probably a consequence of how I set up the bid structure.

Switching the average number of items to an average of 15 of each good type, per bidder, means that more combinations of bids are feasible. With that adjustment,

100 bidders: 0.3 seconds
1000 bidders: 21.6 seconds
3000 bidders: 13.2 seconds (an easy case?), 53.2 seconds
10000 bidders: 78.8 seconds

Obviously these numbers would be better if I ran more than one example of each. ;) Although these numbers are pretty good for a single instance of the winner-determination problem (and my computer is none too speedy by today's standards) a 1000-bidder auction would require up to 2000 runs of the WDP to calculate the VCG prices, so there is plenty of room for improvement. (glpsol doesn't let you specify a starting basis but the library API does, so in practice you could provide a good starting point once you'd solved the original problem.)
Tags: auctions, glpk, linear programming, software
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.