×

On the product knapsack problem. (English) Zbl 1404.90110

Summary: Given a set of items, each characterized by a profit and a weight, we study the problem of maximizing the product of the profits of the selected items, while respecting a given capacity. To the best of our knowledge this is the first manuscript that studies this variant of the knapsack problem which we call product knapsack problem (PKP). We show that PKP is weakly NP-hard. We propose and implement a dynamic programming algorithm and different mixed integer linear and nonlinear programming formulations for the PKP. Finally, we present an extensive computational study on a large set of benchmark instances derived from the literature.

MSC:

90C27 Combinatorial optimization
90C39 Dynamic programming
90C11 Mixed integer programming

Software:

Knapsack; ANTIGONE
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balas, E; Zemel, E, An algorithm for large zero-one knapsack problems, Oper. Res., 28, 1130-1154, (1980) · Zbl 0449.90064 · doi:10.1287/opre.28.5.1130
[2] Bellman, R.: Dynamic Programming. Princeton University Press, Princeton (1957) · Zbl 0077.13605
[3] Belotti, P; Lee, J; Liberti, L; Margot, F; Wächter, A, Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., 24, 597-634, (2009) · Zbl 1179.90237 · doi:10.1080/10556780903087124
[4] Bettinelli, A., Cacchiani, V., Malaguti, E.: A branch-and-bound algorithm for the knapsack problem with conflict graph. Technical report (2016) · Zbl 1386.90123
[5] Brams, JS; Kilgour, MD; Zwicker, SW, The paradox of multiple elections, Soc. Choice Welf., 15, 211-236, (1998) · Zbl 1066.91516 · doi:10.1007/s003550050101
[6] Buchheim, C; Rinaldi, G, Efficient reduction of polynomial zero-one optimization to the quadratic case, SIAM J. Optim., 18, 1398-1413, (2007) · Zbl 1165.90685 · doi:10.1137/050646500
[7] Caprara, A; Pisinger, D; Toth, P, Exact solution of the quadratic knapsack problems, INFORMS J. Comput., 11, 125-137, (1998) · Zbl 1034.90521 · doi:10.1287/ijoc.11.2.125
[8] Chevaleyre, Y., Endriss, U., Lang, J., Maudet, N.: A short introduction to computational social choice. In: van Leeuwen, J., Italiano, G.F., van der Hoek, W., Meinel, C., Sack, H., Plášil, F. (eds.) SOFSEM 2007: Theory and Practice of Computer Science. SOFSEM 2007. Lecture Notes in Computer Science, vol 4362. Springer, Berlin, Heidelberg (2007) · Zbl 1131.91316
[9] D’Ambrosio, C; Martello, S, Heuristic algorithms for the general nonlinear separable knapsack problem, Comput. Oper. Res., 38, 505-513, (2011) · Zbl 1231.90320 · doi:10.1016/j.cor.2010.07.010
[10] Dantzig, G, Discrete variable extremum problems, Oper. Res., 5, 266-277, (1957) · Zbl 1414.90353 · doi:10.1287/opre.5.2.266
[11] Gallo, G; Hammer, P; Simeone, B, Quadratic knapsack problems, Math. Program. Study, 12, 132-149, (1980) · Zbl 0462.90068 · doi:10.1007/BFb0120892
[12] Hao, J., Leung, H.: Interactions in Multiagent Systems: Fairness, Social Optimality and Individual Rationality, chap. Fairness in Cooperative Multiagent Systems. Springer, Berlin (2016) · Zbl 1336.68003 · doi:10.1007/978-3-662-49470-7
[13] Horowitz, E; Sahni, S, Computing partitions with applications to the knapsack problem, J. ACM, 21, 277-292, (1974) · Zbl 0329.90046 · doi:10.1145/321812.321823
[14] Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004) · Zbl 1103.90003 · doi:10.1007/978-3-540-24777-7
[15] Martello, S; Pisinger, D; Toth, P, Dynamic programming and strong bounds for the 0-1 knapsack problem, Manag. Sci., 45, 414-424, (1999) · Zbl 1231.90338 · doi:10.1287/mnsc.45.3.414
[16] Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, Chichester (1990) · Zbl 0708.68002
[17] Misener, R; Floudas, CA, ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 503-526, (2014) · Zbl 1301.90063 · doi:10.1007/s10898-014-0166-2
[18] Pisinger, D, The quadratic knapsack problem—a survey, Discrete Appl. Math., 155, 623-648, (2007) · Zbl 1143.90028 · doi:10.1016/j.dam.2006.08.007
[19] Pisinger, D; Rasmussen, A; Sandvik, R, Solution of large quadratic knapsack problems through aggressive reduction, INFORMS J. Comput., 19, 280-290, (2007) · Zbl 1241.90119 · doi:10.1287/ijoc.1050.0172
[20] Rosenberg, IG, Reduction of bivalent maximization to the quadratic case, Cahiers du Centre d’Etudes de Recherche Opérationelle, 17, 71-74, (1975) · Zbl 0302.90041
[21] Sadykov, R; Vanderbeck, F, Bin packing with conflicts: a generic branch-and-price algorithm, INFORMS J. Comput., 25, 244-255, (2013) · doi:10.1287/ijoc.1120.0499
[22] Tawarmalani, M; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047 · doi:10.1007/s10107-005-0581-8
[23] Uckelman, J, Alice and bob will fight: the problem of electing a committee in the presence of candidate interdependence, Front. Artif. Intell. Appl., 215, 1023-1024, (2010)
[24] Yamada, T; Kataoka, S; Watanabe, K, Heuristic and exact algorithms for the disjunctively constrained knapsack problem, Inf. Process. Soc. Jpn. J., 43, 2864-2870, (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.