Greedy, genetic, and greedy genetic algorithms for the quadratic knapsack problem

ABSTRACT

Augmenting an evolutionary algorithm with knowledge of its target problem can yield a more effective algorithm, as this presentation illustrates. The Quadratic Knapsack Problem extends the familiar Knapsack Problem by assigning values not only to individual objects but also to pairs of objects. In these problems, an object's value density is the sum of the values associated with it divided by its weight. Two greedy heuristics for the quadratic problem examine objects for inclusion in the knapsack in descending order of their value densities. Two genetic algorithms encode candidate selections of objects as binary strings and generate only strings whose selections of objects have total weight no more than the knapsack's capacity. One GA is naive; its operators apply no information about the values associated with objects. The second extends the naive GA with greedy techniques from the non-evolutionary heuristics. Its operators examine objects for inclusion in the knapsack in orders determined by tournaments based on objects' value densities. All four algorithms are tested on twenty problem instances whose optimum knapsack values are known. The greedy heuristics do well, as does the naive GA, but the greedy GA exhibits the best performance. In repeated trials on the test instances, it identifies optimum solutions more than nine times out of every ten.

References

1. A. Billionnet, A. Faye, and E. Soutif. An exact algorithm for the 0-1 quadratic knapsack problem. In ISMP'97, Lausanne, Switzerland, 1997.
2. Alain Billionnet and Éric Soutif. An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem. European Journal of Operational Research, 157(3):565--575, 2004.
3. Alain Billionnet and Éric Soutif. Using a mixed integer programming tool for solving the 0-1 quadratic knapsack problem. INFORMS Journal on Computing, 16(2):188--197, 2004.
4. Alberto Caprara, David Pisinger, and Paolo Toth. Exact solution of the quadratic knapsack problem. INFORMS Journal on Computing, 11:125--137, 1999.
5. P. C. Chu and J. B. Beasley. A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristics, 4:63--86, 1998.
6. Zvi Drezner, Peter M. Hahn, and Éric D. Taillard. A study of quadratic assignment problem instances that are difficult for meta-heuristic methods. Technical report, INA, Yverdon-les-bains, 2002. INA technical report.
7. C. E. Ferreira, A. Martin, C. C. de Souza, R. Weismantel, and L. A. Wolsey. Formulations and valid inequalities for node capacitated graph partitioning. Mathematical Programming, 74:247--266, 1996.
8. G. Gallo, P. L. Hammer, and B. Simeone. Quadratic knapsack problems. Mathematical Programming, 12:132--149, 1980.
9. Michael R. Garey and David S. Johnson. Computers and Intractibility: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, 1979.
10. Jens Gottlieb and Günther R. Raidl. Characterizing locality in decoder-based EAs for the Multidimensional Knapsack Problem. In Cyril Fonlupt, Jin-Kao Hao, Evelyne Lutton, Edmund Ronald, and Marc Schoenauer, editors, AE'99: Selected Papers form the 4th European Conference on Artificial Evolution, pages 38--52, Berlin, 2000. Springer-Verlag.
11. Peter L. Hammer and David J. Rader, Jr. Efficient methods for solving quadratic 0-1 knapsack problems. INFOR, 35(3):170--182, 1997.
12. C. Helmberg, F. Rendl, and R. Weismantel. A semidefinite programming approach to the quadratic knapsack problem. Journal of Combinatorial Optimization, 4(2):197--215, 2000.
13. E. L. Johnson, A. Mehrotra, and G. L. Nemhauser. Min-cut clustering. Mathematical Programming, 62:133--152, 1993.
14. Kengo Katayama and Hiroyuki Narihisa. On fundamental design of parthenogenetic algorithm for the binary quadratic programming problem. In Congress on Evolutionary Computation 2001 Proceedings, pages 356--363. IEEE, May 2001.
15. Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack Problems. Springer, Berlin, 2004.
16. Sami Khuri, Thomas Bäck, and Jörg Heitkötter. The zero/one multiple knapsack problem and genetic algorithms. In Ed Deaton, Dave Oppenheim, Joseph Urban, and Hal Berghel, editors, Applied Computing 1994: Proceedings of the 1994 ACM Symposium on Applied Computing, pages 188--193, New York, 1994. ACM Press.
17. D. L. Laughhunn. Quadratic binary programming with applications to capital budgeting problems. Operations Research, 18:454--461, 1970.
18. Andrea Lodi, Kim Allemand, and Thomas M. Liebling. An evolutionary heuristic for quadratic 0-1 programming. European Journal of Operational Research, 119:662--670, 1999.
19. Peter Merz and Bernd Freisleben. Genetic algorithms for binary quadratic programming. In Wolfgang Banzhaf et~al., editor, Proceedings of the Genetic and Evolutionary Computation Conference, pages 417--424, San Francisco, CA, 1999. Morgan Kaufman.
20. Peter Merz and Bernd Freisleben. Memetic algorithms for the unconstrained binary quadratic programming problem. BioSystems, 78(1--3):99--118, 2004.
21. K. Park, K. Lee, and S. Park. An extended formulation approach to the edge-weighted maximal clique problem. European Journal of Operational Research, 95:671--682, 1996.
22. Günther R. Raidl. An improved genetic algorithm for the Multiconstrained 0-1 Knapsack Problem. In The 1998 IEEE Intermational Conference on Evolutionary Computation Proceedings, pages 207--211, Piscataway, NJ, May 1998. IEEE.
23. Günther R. Raidl. Weight-codings in a genetic algorithm for the multiconstrained knapsack problem. In Proceedings of the 1999 Congress on Evolutionary Computation CEC99, pages 596--603, Piscataway, NJ, 1999. IEEE Press.
24. J. Rhys. A selection problem of shared fixed costs and network flows. Management Science, 17:200--207, 1970.

Index Terms

• Computing methodologies

  • Machine learning

• Mathematics of computing

  • Discrete mathematics

    • Combinatorics

  • Mathematical analysis

    • Mathematical optimization

• Theory of computation

  • Design and analysis of algorithms

    • Mathematical optimization