pith. sign in

arxiv: 2604.05232 · v1 · submitted 2026-04-06 · 💻 cs.DS

Solving Hard Instances from Knapsack and Bounded Knapsack Problems: A new state-of-the-art solver

Renan F. F. da Silva , Thiago A. de Queiroz , Rafael C. S. Schouery This is my paper

Pith reviewed 2026-05-10 18:37 UTC · model grok-4.3

classification 💻 cs.DS
keywords knapsack problembounded knapsack problemdynamic programmingoptimization solvercore algorithmmultiplicity reductiondivisibility boundstate-of-the-art solver
0
0 comments X

The pith

RECORD introduces refined dynamic programming techniques that solve difficult knapsack and bounded knapsack instances substantially faster than prior solvers.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces RECORD, a new solver for the Knapsack Problem and Bounded Knapsack Problem that refines core-based dynamic programming. It adds multiplicity reduction to limit item types, a new divisibility bound for better fixing, and other enhancements like on-the-fly aggregation. Experiments demonstrate that these changes yield major speed gains on hard benchmark instances while keeping good performance on easier ones. This matters because faster exact solvers for these NP-hard problems can handle larger practical instances in areas like resource allocation and scheduling.

Core claim

The authors claim that their RECORD solver, by integrating multiplicity reduction, divisibility bounds, and refined dominance fixing into core and state-based dynamic programming, overcomes limitations of previous approaches and delivers consistent outperformance on challenging KP and BKP instances, often by several orders of magnitude, while preserving near-linear runtime on typical cases.

What carries the argument

Refined Core-based Dynamic Programming with multiplicity reduction and divisibility bound, which limits the number of distinct item types and strengthens item fixing and symmetry breaking during the search.

If this is right

  • RECORD solves more hard instances within practical time limits compared to earlier methods.
  • The new components maintain efficiency on easy instances while boosting performance on difficult ones.
  • Practical applications can now tackle larger knapsack problems exactly.
  • The approach suggests that targeted refinements to bounding and reduction techniques can advance exact solvers for NP-hard problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the gains generalize, similar multiplicity and divisibility ideas might improve solvers for related problems like the unbounded knapsack.
  • Instance-specific preprocessing could be further automated based on these reductions.
  • Future work might combine this with parallel computing to scale to even larger instances.

Load-bearing premise

The performance improvements on the selected benchmark sets result from the new algorithmic strategies rather than implementation specifics or unrepresentative test data.

What would settle it

A set of new hard knapsack benchmark instances where RECORD does not show consistent speed advantages over the previous best solvers would falsify the claim of establishing a new state of the art.

Figures

Figures reproduced from arXiv: 2604.05232 by Rafael C. S. Schouery, Renan F. F. da Silva, Thiago A. de Queiroz.

Figure 1
Figure 1. Figure 1: presents two comparison plots. The left plot compares the average runtimes of COMBO and RECORD when the Pisinger instances are grouped by class, number of items, and range parame￾ter. Under this aggregation, RECORD is at most twice as slow, and its average runtime never exceeds 20 ms. In contrast, COMBO is slower in several groups by factors larger than 2 and sometimes greater than 10, with runtimes reachi… view at source ↗
read the original abstract

The Knapsack Problem (KP) and its generalization, the Bounded Knapsack Problem (BKP), are classical NP-hard problems with numerous practical applications, and despite being introduced over 25 years ago, the solvers COMBO and BOUKNAP remain the state of the art due to their highly optimized implementations and sophisticated bounding techniques. In this work, we present RECORD (Refined Core-based Dynamic Programming), a new solver for both problems that builds upon key components of COMBO, including core- and state-based dynamic programming, weak upper bounds, and surrogate relaxation with cardinality constraints, while introducing novel strategies to overcome its limitations. In particular, we propose multiplicity reduction to limit the number of distinct item types, combined with on-the-fly item aggregation, refined fixing-by-dominance techniques, and a new divisibility bound that strengthens item fixing and symmetry breaking. These enhancements allow RECORD to preserve COMBO's near-linear-time behavior on most instances while achieving substantial speedups on more challenging cases, and computational experiments show that it consistently outperforms both COMBO and BOUKNAP on difficult benchmark sets, often by several orders of magnitude, establishing a new state-of-the-art solver for KP and BKP.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper presents RECORD (Refined Core-based Dynamic Programming), a new solver for the Knapsack Problem (KP) and Bounded Knapsack Problem (BKP). It builds on COMBO by adding multiplicity reduction with on-the-fly aggregation, refined dominance fixing, and a new divisibility bound for symmetry breaking and item fixing. The central claim is that RECORD preserves COMBO's near-linear behavior on easy instances while delivering orders-of-magnitude speedups on difficult benchmarks, consistently outperforming both COMBO and BOUKNAP and establishing a new state-of-the-art.

Significance. If the performance claims are robustly supported, the work would be significant for combinatorial optimization, as it targets long-standing practical solvers for these NP-hard problems with targeted algorithmic refinements. The approach of extending core-based DP with new bounding and reduction techniques is a natural evolution, and successful validation could influence exact methods for related packing problems.

major comments (2)
  1. [Computational Experiments] The computational experiments section provides no ablation studies that disable the new components (multiplicity reduction, divisibility bound, refined dominance fixing) one at a time against an otherwise identical baseline implementation. This leaves the causal attribution of the reported speedups insecure, as gains could stem from unmentioned data structures, coding practices, or compiler settings rather than the listed innovations.
  2. [Abstract and Experimental Setup] No details are given on benchmark selection criteria for the 'difficult' sets, hardware platform, number of independent runs, statistical significance testing, or availability of code and instance data. These omissions make it impossible to assess whether the orders-of-magnitude outperformance generalizes or is reproducible, directly weakening the central empirical claim.
minor comments (2)
  1. [Algorithm Description] The description of the new divisibility bound would benefit from explicit pseudocode or a short proof sketch showing how it strengthens fixing and symmetry breaking beyond existing bounds.
  2. [Introduction] Standard references to the original COMBO and BOUKNAP papers should be included when describing the baseline components being extended.

Simulated Author's Rebuttal

2 responses · 0 unresolved

Thank you for the referee's constructive comments on our manuscript describing RECORD. We address each major comment below and outline the revisions we will undertake.

read point-by-point responses

  1. Referee: [Computational Experiments] The computational experiments section provides no ablation studies that disable the new components (multiplicity reduction, divisibility bound, refined dominance fixing) one at a time against an otherwise identical baseline implementation. This leaves the causal attribution of the reported speedups insecure, as gains could stem from unmentioned data structures, coding practices, or compiler settings rather than the listed innovations.

    Authors: We agree that ablation studies would provide stronger evidence for attributing performance gains specifically to the proposed techniques rather than implementation details. The manuscript presents direct comparisons of the full RECORD solver against COMBO and BOUKNAP, but to address this concern we will add ablation experiments in the revised version. These will disable each new component (multiplicity reduction with on-the-fly aggregation, refined dominance fixing, and the divisibility bound) one at a time while keeping all other aspects identical, and report the resulting runtimes on the same hard benchmark instances. revision: yes

  2. Referee: [Abstract and Experimental Setup] No details are given on benchmark selection criteria for the 'difficult' sets, hardware platform, number of independent runs, statistical significance testing, or availability of code and instance data. These omissions make it impossible to assess whether the orders-of-magnitude outperformance generalizes or is reproducible, directly weakening the central empirical claim.

    Authors: We acknowledge that these experimental details are essential for assessing reproducibility and generalizability. In the revised manuscript we will expand the experimental setup to explicitly describe the criteria used to identify the difficult benchmark sets, the hardware platform and its specifications (CPU, memory, OS), the number of independent runs performed, any statistical significance tests applied, and we will make the RECORD source code and all benchmark instances publicly available via a repository link upon acceptance. revision: yes

Circularity Check

0 steps flagged

No circularity: algorithmic description plus empirical benchmarks

full rationale

The paper describes a new DP-based solver (RECORD) that extends COMBO with explicitly listed new components (multiplicity reduction, on-the-fly aggregation, refined dominance, divisibility bound). Correctness rests on standard dynamic-programming arguments that are independent of the new heuristics. Performance claims are purely empirical (timing on benchmark sets) and do not involve any fitted parameters, self-referential definitions, or predictions derived from the authors' own prior results. No equations or uniqueness theorems are invoked that reduce to the paper's own inputs. Self-citations, if present, are limited to the baseline solvers (COMBO, BOUKNAP) whose authors are distinct; they supply external reference implementations rather than load-bearing justification for RECORD's innovations.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The solver rests on the standard correctness of dynamic programming for knapsack problems and the validity of surrogate relaxation and bounding techniques already present in COMBO; no new free parameters, axioms, or invented entities are introduced beyond those inherited from prior literature.

pith-pipeline@v0.9.0 · 5532 in / 1225 out tokens · 36328 ms · 2026-05-10T18:37:55.032055+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    Operations Research 28(5):1130--1154, doi: 10.1287/opre.28.5.1130

    Balas E, Zemel E (1980) An algorithm for large zero-one knapsack problems. Operations Research 28(5):1130--1154, doi: 10.1287/opre.28.5.1130

    work page doi:10.1287/opre.28.5.1130 1980

  2. [2]

    INFORMS Journal on Computing 36(1):141--162, doi: 10.1287/ijoc.2022.0257

    Baldacci R, Coniglio S, Cordeau JF, Furini F (2024) A numerically exact algorithm for the bin-packing problem. INFORMS Journal on Computing 36(1):141--162, doi: 10.1287/ijoc.2022.0257

    work page doi:10.1287/ijoc.2022.0257 2024

  3. [3]

    part i: Single knapsack problems

    Cacchiani V, Iori M, Locatelli A, Martello S (2022) Knapsack problems — an overview of recent advances. part i: Single knapsack problems. Computers & Operations Research 143:105692, doi: 10.1016/j.cor.2021.105692

    work page doi:10.1016/j.cor.2021.105692 2022

  4. [4]

    European Journal of Operational Research 289(2):435--455, doi: 10.1016/j.ejor.2020.07.023

    Coniglio S, Furini F, San Segundo P (2021) A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts. European Journal of Operational Research 289(2):435--455, doi: 10.1016/j.ejor.2020.07.023

    work page doi:10.1016/j.ejor.2020.07.023 2021

  5. [5]

    Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to Algorithms (MIT Press), 3rd edition

    work page 2009

  6. [6]

    INFORMS Journal on Computing doi:10.1287/ ijoc.2023.0399

    da Silva RFF, Schouery RCS (2025) Solving cutting stock problems via an extended ryan-foster branching scheme and fast column generation. INFORMS Journal on Computing ijoc.2023.0399, doi: 10.1287/ijoc.2023.0399

    work page doi:10.1287/ijoc.2023.0399 2025

  7. [7]

    Methods of Operations Research 36(1):49--60

    Dembo RS, Hammer PL (1980) A reduction algorithm for knapsack problems. Methods of Operations Research 36(1):49--60

    work page 1980

  8. [8]

    Operations Research 23(3):434--451, doi: 10.1287/opre.23.3.434

    Glover F (1975) Surrogate constraint duality in mathematical programming. Operations Research 23(3):434--451, doi: 10.1287/opre.23.3.434

    work page doi:10.1287/opre.23.3.434 1975

  9. [9]

    European Journal of Operational Research 301(3):841--854, doi: 10.1016/j.ejor.2021.12.009

    Jooken J, Leyman P, De Causmaecker P (2022) A new class of hard problem instances for the 0–1 knapsack problem. European Journal of Operational Research 301(3):841--854, doi: 10.1016/j.ejor.2021.12.009

    work page doi:10.1016/j.ejor.2021.12.009 2022

  10. [10]

    Kellerer H, Pferschy U, Pisinger D (2004) Multidimensional Knapsack Problems, 235--283 (Berlin, Heidelberg: Springer Berlin Heidelberg), doi: 10.1007/978-3-540-24777-7\_9

    work page doi:10.1007/978-3-540-24777-7 2004

  11. [11]

    INFORMS Journal on Computing 34(6):3134--3150, doi: 10.1287/ijoc.2022.1223

    Lalonde O, C\^ o t\' e JF, Gendron B (2022) A branch-and-price algorithm for the multiple knapsack problem. INFORMS Journal on Computing 34(6):3134--3150, doi: 10.1287/ijoc.2022.1223

    work page doi:10.1287/ijoc.2022.1223 2022

  12. [12]

    INFORMS Journal on Computing 34(4):2249--2270, doi: 10.1287/ijoc.2022.1165

    Letelier OR, Clautiaux F, Sadykov R (2022) Bin packing problem with time lags. INFORMS Journal on Computing 34(4):2249--2270, doi: 10.1287/ijoc.2022.1165

    work page doi:10.1287/ijoc.2022.1165 2022

  13. [13]

    Management Science 45(3):414--424, doi: 10.1287/mnsc.45.3.414

    Martello S, Pisinger D, Toth P (1999) Dynamic programming and strong bounds for the 0-1 knapsack problem. Management Science 45(3):414--424, doi: 10.1287/mnsc.45.3.414

    work page doi:10.1287/mnsc.45.3.414 1999

  14. [14]

    Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations (USA: John Wiley & Sons, Inc.)

    work page 1990

  15. [15]

    Operations Research 45(5):768--778, doi: 10.1287/opre.45.5.768

    Martello S, Toth P (1997) Upper bounds and algorithms for hard 0-1 knapsack problems. Operations Research 45(5):768--778, doi: 10.1287/opre.45.5.768

    work page doi:10.1287/opre.45.5.768 1997

  16. [16]

    INFORMS Journal on Computing 26(4):704--717, doi: 10.1287/ijoc.2014.0593

    Morrison DR, Sauppe JJ, Sewell EC, Jacobson SH (2014) A wide branching strategy for the graph coloring problem. INFORMS Journal on Computing 26(4):704--717, doi: 10.1287/ijoc.2014.0593

    work page doi:10.1287/ijoc.2014.0593 2014

  17. [17]

    Mathematical Progra mming 183(1), 483– 523 (Sep 2020)

    Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2020) A generic exact solver for vehicle routing and related problems. Mathematical Programming 183(1):483--523, doi: 10.1007/s10107-020-01523-z

    work page doi:10.1007/s10107-020-01523-z 2020

  18. [18]

    European Journal of Operational Research 87(1):175--187, doi: 10.1016/0377-2217(94)00013-3

    Pisinger D (1995) An expanding-core algorithm for the exact 0–1 knapsack problem. European Journal of Operational Research 87(1):175--187, doi: 10.1016/0377-2217(94)00013-3

    work page doi:10.1016/0377-2217(94)00013-3 1995

  19. [19]

    Operations Research 45(5):758--767, doi: 10.1287/opre.45.5.758

    Pisinger D (1997) A minimal algorithm for the 0-1 knapsack problem. Operations Research 45(5):758--767, doi: 10.1287/opre.45.5.758

    work page doi:10.1287/opre.45.5.758 1997

  20. [20]

    European Journal of Operational Research 114(3):528--541, doi: 10.1016/S0377-2217(98)00120-9

    Pisinger D (1999) An exact algorithm for large multiple knapsack problems. European Journal of Operational Research 114(3):528--541, doi: 10.1016/S0377-2217(98)00120-9

    work page doi:10.1016/s0377-2217(98)00120-9 1999

  21. [21]

    INFORMS Journal on Computing 12(1):75--82, doi: 10.1287/ijoc.12.1.75.11898

    Pisinger D (2000) A minimal algorithm for the bounded knapsack problem. INFORMS Journal on Computing 12(1):75--82, doi: 10.1287/ijoc.12.1.75.11898

    work page doi:10.1287/ijoc.12.1.75.11898 2000

  22. [22]

    Pisinger D (2005) Where are the hard knapsack problems? Computers & Operations Research 32(9):2271--2284, doi: 10.1016/j.cor.2004.03.002

    work page doi:10.1016/j.cor.2004.03.002 2005

  23. [23]

    INFORMS Journal on Computing 25(2):244--255, doi: 10.1287/ijoc.1120.0499

    Sadykov R, Vanderbeck F (2013) Bin packing with conflicts: A generic branch-and-price algorithm. INFORMS Journal on Computing 25(2):244--255, doi: 10.1287/ijoc.1120.0499

    work page doi:10.1287/ijoc.1120.0499 2013

  24. [24]

    Computers & Operations Research 128:105184, doi: 10.1016/j.cor.2020.105184

    Smith-Miles K, Christiansen J, Muñoz MA (2021) Revisiting where are the hard knapsack problems? via instance space analysis. Computers & Operations Research 128:105184, doi: 10.1016/j.cor.2020.105184

    work page doi:10.1016/j.cor.2020.105184 2021

  25. [25]

    INFORMS Journal on Computing 32, 428–443

    Wei L, Luo Z, Baldacci R, Lim A (2020) A new branch-and-price-and-cut algorithm for one-dimensional bin-packing problems. INFORMS Journal on Computing 32(2):428--443, doi: 10.1287/ijoc.2018.0867

    work page doi:10.1287/ijoc.2018.0867 2020