A New Primal-Dual Genetic Algorithm: Case Study for the Winner Determination Problem

1. Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Kluwer Academic Publishers, Boston (1989)

   MATH  Google Scholar 

2. Yang, S.: PDGA: the Primal-Dual Genetic Algorithm. In: Abraham, A., Koppen, M., Franke, K. (eds.) Design and Application of Hybrid Intelligent Systems, pp. 214–223. IOS Press, Amsterdam (2003)

   Google Scholar 

3. Raidl, G., Puchinger, J.: Combining (Integer) Linear Programming Techniques and Metaheuristics for Combinatorial Optimization. In: Blum, C., Blesa Aguilera, M.J., Roli, A., Sampels, M. (eds.) Hybrid Metaheuristics, An Emerging Approach to Optimization, Studies in Computational Intelligence, vol.114, pp. 31–62 (2008)

   Google Scholar 

4. Pfeiffer, J., Rothlauf, F.: Analysis of Greedy Heuristics and Weight-Coded EAs for Multidimensional Knapsack Problems and Multi-Unit Combinatorial Auctions. In: Proceedings of the 9th annual Conference on Genetic and Evolutionary Computation, p.1529 (2007)

   Google Scholar 

5. Hansen, P., Brimberg, J., Mladenović, N., Urosević, D.: Primal-dual variable neighbourhood search for the simple plant location problem. INFORMS Journal on Computing 19(4), 552–564 (2007)

   Article  MathSciNet  Google Scholar 

6. Dantzig, G.B., Ford, L.R., Fulkerson, D.R.: A primal-dual algorithm for linear programs. In: Kuhn, H.W., Tucker, A.W. (eds.) Linear Inequalities and Related Systems, pp. 171–181. Princeton University Press, Princeton (1956)

   Google Scholar 

7. Williamson, D.P.: The Primal-Dual Method for Approximation Algorithms. Mathematical Programming, Series B 91(3), 447–478 (2002)

   Article  MATH  Google Scholar 

8. Fujishima, Y., Leyton-Brown, K., Shoham, Y.: Taming the computational complexity of combinatorial auctions: optimal and approximate approaches. In: Sixteenth international joint conference on artificial intelligence, pp. 48–53 (1999)

   Google Scholar 

9. Sandholm, T., Suri, S., Gilpin, A., Levine, D.: CABoB: a fast optimal algorithm for combinatorial auctions. In: Proceedings of the international joint conferences on artificial intelligence, pp. 1102–1108 (2001)

   Google Scholar 

10. Nisan, N.: Bidding and Allocation in Combinatorial Auctions. In: Proceedings of ACM conference on electronic commerce EC, pp. 1–12 (2000)

    Google Scholar 

11. Andersson, A., Tenhunen, M., Ygge, F.: Integer programming for combinatorial auction winner determination. In: 4th Internationl Conference on Multiagent Systems (2000)

    Google Scholar 

12. Hoos, H.H., Boutilier, C.: Solving combinatorial auctions using stochastic local search. In: Proceedings of the 17th national conference on artificial intelligence, pp. 22–29 (2000)

    Google Scholar 

13. Guo, Y., Lim, A., Rodrigues, B., Zhu, Y.: Heuristics for a bidding problem. Computers and Operations Research 33(8), 2179–2188 (2006)

    Article  MATH  Google Scholar 

14. Boughaci, D., Benhamou, B., Drias, H.: A memetic algorithm for the optimal winner determination problem. Soft Computing 13(8-9), 905–917 (2009)

    Article  Google Scholar 

15. Vohra, R., de Vries, S.: Combinatorial auctions: A survey. INFORMS Journals of Computing 15(3), 284–309 (2003)

    Article  Google Scholar 

16. Rothkopf, M.H., Pekec, A., Harstad, R.M.: Computationally manageable combinatorial auctions. Management Science 44(8), 1131–1147 (1998)

    Article  MATH  Google Scholar 

17. Gonen, R., Lehmann, D.: Linear Programming helps solving large multi-unit combinatorial auctions. In: Proceedings of the Electronic Market Design Workshop (2001)

    Google Scholar 

18. DeMartini, C., Kwasnica, A.M., Ledyard, O., Porter, D.: A New and Improved Design for Multi-Object Iterative Auctions. Management Science 51(3), 419–434 (2005)

    Article  Google Scholar 

19. Gottlieb, J.: Permutation-based evolutionary algorithms for multidimensional knapsack problems. In: Proceedings of the 2000 ACM symposium on Applied computing, vol. (1), pp. 408–414 (2000)

    Google Scholar 

20. Davis, L.: Handbook of Genetic Algorithms. Van Nostrand Reinhold (1991)

    Google Scholar 

21. Krysta, P.: Greedy Approximation via Duality for Packing, Combinatorial Auctions and Routing. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 615–627. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

22. Leyton-Brown, K., Pearson, M., Shoham, Y.: Towards a Universal Test Suite for Combinatorial Auction Algorithms. In: Proceedings of the 2nd ACM conference on Electronic commerce, pp. 66–76 (2000)

    Google Scholar 

23. Berkelaar, M.: lp_solve - version 5.5. Eindhoven University of Technology, http://sourceforge.net/projects/lpsolve/

24. Zurel, E., Nisan, N.: An Efficient Approximate Allocation Algorithm for Combinatorial Auctions. In: Proceedings of the 3rd ACM conference on Electronic commerce, pp. 125–136 (2001)

    Google Scholar 

Download references