Knapsack swMATH ID: 4723 Software Authors: Pisinger, David; Toth, Paolo Description: Knapsack problems are the simplest NP-hard problems in combinatorial optimization, as they maximize an objective function subject to a single resource constraint. Several variants of the classical 0-1 knapsack problem will be considered with respect to relaxations, bounds, reductions and other algorithmic techniques for the exact solution. Computational results are presented to compare the actual performance of the most effective algorithms published. Homepage: http://www.diku.dk/~pisinger/codes.html Keywords: survey; knapsack problems; NP-hard problems; relaxations; bounds Related Software: CPLEX; MULKNAP; OR-Library; Gurobi; Tabu search; SCIP; GitHub; Quicksort; Scatter Search; DIMACS; MINTO; SSCFLPsolver; VRPSolver; SPOT; TSPLIB; MIPLIB; VRP; QuadProgBB; MATILDA; BARON Cited in: 557 Documents Standard Articles 3 Publications describing the Software, including 3 Publications in zbMATH Year The quadratic knapsack problem – a survey. Zbl 1143.90028Pisinger, David 2007 Knapsack problems. Zbl 1103.90003Kellerer, Hans; Pferschy, Ulrich; Pisinger, David 2004 Knapsack problems. Zbl 0924.90120Pisinger, David; Toth, Paolo 1998 all top 5 Cited by 981 Authors 28 Pisinger, David 16 Pferschy, Ulrich 14 Hifi, Mhand 13 Figueira, José Rui 9 Furini, Fabio 9 Hanafi, Saïd 9 Martello, Silvano 9 Monaci, Michele 8 Iori, Manuel 8 Kellerer, Johann 8 Shachnai, Hadas 8 Toth, Paolo 7 Caprara, Alberto 7 Jansen, Klaus 7 Klose, Andreas 7 Traversi, Emiliano 6 Della Croce, Federico 6 Fréville, Arnaud 6 Raidl, Günther R. 6 Tamir, Tami 5 Ceselli, Alberto 5 Cui, Yaodong 5 Fomeni, Franklin Djeumou 5 Klamroth, Kathrin 5 Letchford, Adam N. 5 Ljubić, Ivana 5 Mhalla, Hedi 5 Prokopyev, Oleg Alexan 5 Sadykov, Ruslan 5 Scatamacchia, Rosario 5 Sinnl, Markus 5 Speranza, Maria Grazia 5 Strusevich, Vitaly A. 5 Vasil’ev, Igor’ Leonidovich 5 Wilbaut, Christophe 4 Antonopoulos, Antonis 4 Arenales, Marcos Nereu 4 Boccia, Maurizio 4 Contardo, Claudio 4 Czibula, Oliver G. 4 Dell’Amico, Mauro 4 Epstein, Leah 4 Fischetti, Matteo 4 Gu, Hanyu 4 Makino, Kazuhisa 4 Mansini, Renata 4 Pagourtzis, Aris T. 4 Paquete, Luís F. 4 Pessoa, Artur Alves 4 Petsalakis, Stavros 4 Puchinger, Jakob 4 Righini, Giovanni 4 Ruzika, Stefan 4 Schulze, Britta 4 Uchoa, Eduardo 4 Vanderbeck, François 4 Vasilakis, Manolis 4 Woeginger, Gerhard 4 Yamada, Takeo 4 Zhang, Bin 4 Zinder, Yakov 3 Boyer, Vincent 3 Chu, Feng 3 Clautiaux, François 3 Climaco, Joao Carlos Namorado 3 Coniglio, Stefano 3 Cordeau, Jean-François 3 Côté, Jean-François 3 D’Ambrosio, Claudia 3 de Causmaecker, Patrick 3 De Smet, Yves 3 El Baz, Didier 3 Elkihel, Moussa 3 Fukunaga, Alex S. 3 Gendron, Bernard 3 Gomes da Silva, Carlos 3 Görtz, Simon 3 Han, Xin 3 Haouari, Mohamed 3 Hoto, Robinson Samuel Vieira 3 Hua, Zhongsheng 3 Jooken, Jorik 3 Kaparis, Konstantinos 3 Korbut, Alexander A. 3 Leus, Roel 3 Levin, Asaf 3 Leyman, Pieter 3 Mansi, Raïd 3 Mavrotas, George 3 Roland, Julien 3 Sbihi, Abdelkader 3 Srikanthan, Thambipillai 3 Stiglmayr, Michael 3 Sun, Xiaoling 3 Wu, Jigang 3 Yang, Zhen 2 Aboolian, Robert 2 Adouani, Yassine 2 Albagli-Kim, Sivan 2 Albert, Laura A. ...and 881 more Authors all top 5 Cited in 96 Serials 105 European Journal of Operational Research 83 Computers & Operations Research 22 Annals of Operations Research 22 INFORMS Journal on Computing 20 Discrete Applied Mathematics 17 Theoretical Computer Science 17 Operations Research Letters 13 Mathematical Programming. Series A. Series B 13 Discrete Optimization 11 Computational Optimization and Applications 10 Journal of Global Optimization 10 Journal of Combinatorial Optimization 8 Optimization Letters 7 Applied Mathematics and Computation 6 Journal of Computer and System Sciences 6 Operations Research 6 Algorithmica 5 Applied Mathematical Modelling 5 4OR 5 Mathematical Programming Computation 4 Information Processing Letters 4 Networks 4 Journal of Computer and Systems Sciences International 4 International Transactions in Operational Research 4 Journal of Heuristics 4 Journal of Scheduling 4 EURO Journal on Computational Optimization 3 Journal of Computational and Applied Mathematics 3 Journal of Optimization Theory and Applications 3 Mathematical and Computer Modelling 3 Automation and Remote Control 3 Engineering Optimization 2 Computing 2 Information Sciences 2 Mathematics and Computers in Simulation 2 Naval Research Logistics 2 Asia-Pacific Journal of Operational Research 2 SIAM Journal on Optimization 2 The Journal of Artificial Intelligence Research (JAIR) 2 Mathematical Methods of Operations Research 2 Informatica (Vilnius) 2 Optimization and Engineering 2 Natural Computing 2 JMMA. Journal of Mathematical Modelling and Algorithms 2 Computer Networks 2 Journal of Discrete Algorithms 1 Acta Informatica 1 American Mathematical Monthly 1 Computers & Mathematics with Applications 1 Automatica 1 Journal of Combinatorial Theory. Series A 1 Kybernetes 1 Management Science 1 Opsearch 1 SIAM Journal on Computing 1 Journal of Algorithms 1 Journal of Information & Optimization Sciences 1 Mathematical Social Sciences 1 International Journal of Production Research 1 SIAM Journal on Discrete Mathematics 1 Journal of Cryptology 1 Journal of Parallel and Distributed Computing 1 Machine Learning 1 Japan Journal of Industrial and Applied Mathematics 1 Games and Economic Behavior 1 International Journal of Computer Mathematics 1 Applied Mathematics. Series B (English Edition) 1 Journal of Mathematical Sciences (New York) 1 Computational and Applied Mathematics 1 The Electronic Journal of Combinatorics 1 Top 1 Annals of Mathematics and Artificial Intelligence 1 Mathematical Problems in Engineering 1 Soft Computing 1 Journal of Shanghai University 1 Far East Journal of Applied Mathematics 1 Data Mining and Knowledge Discovery 1 Discrete Dynamics in Nature and Society 1 CEJOR. Central European Journal of Operations Research 1 Fundamenta Informaticae 1 RAIRO. Operations Research 1 Journal of Applied Mathematics 1 IMA Journal of Management Mathematics 1 Comptes Rendus. Mécanique. Académie des Sciences, Paris 1 Fuzzy Optimization and Decision Making 1 Computational Management Science 1 International Journal of Operational Research 1 Applied and Computational Mathematics 1 International Journal of Mathematics in Operational Research 1 Science China. Mathematics 1 Computer Science Review 1 Journal of Mathematical Modelling and Algorithms in Operations Research 1 Berichte aus der Mathematik 1 SN Operations Research Forum 1 INFOR: Information Systems and Operational Research 1 eXamen.press all top 5 Cited in 21 Fields 510 Operations research, mathematical programming (90-XX) 96 Computer science (68-XX) 30 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 12 Numerical analysis (65-XX) 10 Combinatorics (05-XX) 6 Systems theory; control (93-XX) 4 Calculus of variations and optimal control; optimization (49-XX) 4 Biology and other natural sciences (92-XX) 3 Number theory (11-XX) 3 Information and communication theory, circuits (94-XX) 2 Group theory and generalizations (20-XX) 2 Measure and integration (28-XX) 1 General and overarching topics; collections (00-XX) 1 Mathematical logic and foundations (03-XX) 1 Commutative algebra (13-XX) 1 Convex and discrete geometry (52-XX) 1 Probability theory and stochastic processes (60-XX) 1 Statistics (62-XX) 1 Fluid mechanics (76-XX) 1 Optics, electromagnetic theory (78-XX) 1 Statistical mechanics, structure of matter (82-XX) Citations by Year