Knapsack

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.


References in zbMATH (referenced in 453 articles , 3 standard articles )

Showing results 1 to 20 of 453.
Sorted by year (citations)

1 2 3 ... 21 22 23 next

  1. Dauzère-Pérès, Stéphane; Hassoun, Michael: On the importance of variability when managing metrology capacity (2020)
  2. Della Croce, Federico; Scatamacchia, Rosario: An exact approach for the bilevel knapsack problem with interdiction constraints and extensions (2020)
  3. Drake, John H.; Kheiri, Ahmed; Özcan, Ender; Burke, Edmund K.: Recent advances in selection hyper-heuristics (2020)
  4. Fampa, M.; Lubke, D.; Wang, F.; Wolkowicz, H.: Parametric convex quadratic relaxation of the quadratic knapsack problem (2020)
  5. Goldberg, Noam; Poss, Michael: Maximum probabilistic all-or-nothing paths (2020)
  6. Guignard, Monique: Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic (0-1) optimization problems with linear constraints (2020)
  7. Joung, Seulgi; Lee, Kyungsik: Robust optimization-based heuristic algorithm for the chance-constrained knapsack problem using submodularity (2020)
  8. Morales, Fernando A.; Martínez, Jairo A.: Analysis of divide-and-conquer strategies for the (0-1) minimization knapsack problem (2020)
  9. Anastasiadis, Eleftherios; Deng, Xiaotie; Krysta, Piotr; Li, Minming; Qiao, Han; Zhang, Jinshan: Network pollution games (2019)
  10. Bonami, Pierre; Lodi, Andrea; Schweiger, Jonas; Tramontani, Andrea: Solving quadratic programming by cutting planes (2019)
  11. Coindreau, Marc-Antoine; Gallay, Olivier; Zufferey, Nicolas; Laporte, Gilbert: Integrating workload smoothing and inventory reduction in three intermodal logistics platforms of a European car manufacturer (2019)
  12. Della Croce, Federico; Pferschy, Ulrich; Scatamacchia, Rosario: On approximating the incremental knapsack problem (2019)
  13. Della Croce, Federico; Pferschy, Ulrich; Scatamacchia, Rosario: New exact approaches and approximation results for the penalized knapsack problem (2019)
  14. Dell’Amico, Mauro; Delorme, Maxence; Iori, Manuel; Martello, Silvano: Mathematical models and decomposition methods for the multiple knapsack problem (2019)
  15. Fang, Ethan X.; Liu, Han; Wang, Mengdi: Blessing of massive scale: spatial graphical model estimation with a total cardinality constraint approach (2019)
  16. Furini, Fabio; Traversi, Emiliano: Theoretical and computational study of several linearisation techniques for binary quadratic problems (2019)
  17. Gurski, Frank; Rehs, Carolin; Rethmann, Jochen: Knapsack problems: a parameterized point of view (2019)
  18. Malaguti, Enrico; Monaci, Michele; Paronuzzi, Paolo; Pferschy, Ulrich: Integer optimization with penalized fractional values: the knapsack case (2019)
  19. Ma, Ning; Liu, Ya; Zhou, Zhili: Two heuristics for the capacitated multi-period cutting stock problem with pattern setup cost (2019)
  20. Novak, Antonin; Sucha, Premysl; Hanzalek, Zdenek: Scheduling with uncertain processing times in mixed-criticality systems (2019)

1 2 3 ... 21 22 23 next