On Solving the Knapsack Problem with Conflicts

Derek H. Smith; Roberto Montemanni

REVIEW 2 major objections 5 minor 16 references

On Solving the Knapsack Problem with Conflicts

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read An off-the-shelf mixed-integer linear program solved by the open-source CP-SAT solver matches or beats specialized algorithms for the Knapsack Problem with Conflicts on standard benchmarks.

desk verdict Known MILP plus CP-SAT dominates specialized KPC algorithms on the dense benchmark set, with a real but moderate hardware-asymmetry caveat; worth refereeing after reruns on equal resources. read the letter →

arxiv 2506.03330 v1 pith:3SF75AGJ submitted 2025-06-03 math.OC

Roberto Montemanni , Derek H. Smith This is my paper

classification math.OC MSC 90C1090C27

keywords knapsackproblemwithconflictsconflictgraphCP-SATmixed-integerlinearprogrammingconstraintbranch-and-boundbenchmarkexperimentsopen-sourcesolver

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper sets out to show that a textbook mixed-integer linear program for the Knapsack Problem with Conflicts (KPC), written down directly and handed to the open-source CP-SAT solver, is competitive with, and on most benchmarks faster than, three specialized algorithms built for the problem. The model maximizes total profit subject to a capacity constraint and pairwise conflict constraints $x_i+x_j\le 1$; no custom branching, bounds, or preprocessing is added. On the standard 4,320-instance benchmark with conflict-graph densities from 0.1 to 0.9, CP-SAT proves optimality on every instance class in average seconds, while the best competing method sometimes leaves instances unsolved and takes much longer. On a second benchmark of very sparse conflict graphs (densities 0.001 to 0.05), CP-SAT remains competitive but is slightly inferior to an integer-programming baseline at the hardest densities. If the claim holds, a problem that has motivated a decade of bespoke algorithms can be handled by a generic modeling-plus-solver approach.

What carries the argument

The load-bearing object is the elementary conflict-knapsack MILP: a binary variable $x_i$ for each item, a linear capacity inequality, and one inequality $x_i+x_j\le 1$ for each edge of the conflict graph. The mechanism that carries the argument is CP-SAT, a generic open-source constraint-programming solver into which this model is passed directly. The model's work is to make every feasibility and objective consideration of KPC visible to the solver as linear constraints, so the solver's built-in propagators, clause learning, and search heuristics can exploit the structure of the conflict graph without any problem-specific code.

What would settle it

Rerun CFS, BCM, and the best ILP model under the same conditions as CP-SAT—same machine, same core count, same 600-second limit—on the first 4,320-instance benchmark. If ILP or CFS then proves optimality on instances CP-SAT handles quickly, or if the average-time gap falls by an order of magnitude, the claimed dominance is an artifact of hardware allocation rather than of the modeling approach.

Watch

Extended reading notes

Core claim

The paper's central claim is that the known MILP formulation for KPC—maximize $\sum_{i\in V} p_i x_i$ subject to $\sum_{i\in V} w_i x_i \le c$ and $x_i+x_j\le 1$ for every conflict edge $\{i,j\}\in E$, with $x_i\in\{0,1\}$—when solved by CP-SAT, a generic constraint-programming-based solver, achieves results comparable with and often better than the state of the art. In the first benchmark set, CP-SAT solves all 90 instances in each of the eight classes for every profit and capacity variant, averaging 1.3 seconds per instance, whereas the combinatorial branch-and-bound algorithm CFS solves 86.8, the branch-and-bound algorithm BCM solves 84.6, and the best integer-programming baseline ILP solves 76.2, with average times of 4.8, 8.2, and 54.6 seconds respectively. In the second, very sparse benchmark, CP-SAT's average optimality counts (7.0 of 10 for correlated, 9.1 for random) fall slightly below the ILP baseline (8.3 and 9.5), and the paper attributes the difference to extreme low densities, where ILP is the better choice. The paper concludes that, apart from such extreme cases, the generic approach is preferable despite its minimal implementation effort.

Load-bearing premise

The comparison assumes the published runtimes of CFS, BCM, and ILP are fair baselines even though they were measured on a single core of a roughly 10% slower processor, whereas CP-SAT used all cores; the paper asserts this will not change the outcome without re-running the competitors under matched conditions.

Editorial extensions

If this is right

On the first benchmark set (densities 0.1–0.9, capacities 1×, 3×, 10×, random and correlated profits), CP-SAT proves optimality on all 4,320 instances, with per-class average times between 0.0 and 14.5 seconds and a grand average of 1.3 seconds.
CFS, BCM, and the ILP baseline all leave some first-benchmark instances unproven within the 600-second limit, while CP-SAT does not.
On the sparse second benchmark, the ILP baseline outperforms CP-SAT at densities around 0.02 and 0.05 on large or high-capacity instances, so the generic approach is not uniformly dominant.
Because the MILP needs no custom machinery, applying the approach to KPC variants requires only changing the model, not rewriting an algorithm.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper: if a same-machine, same-core rerun confirms the margins, specialized exact algorithms for KPC become hard to justify for these benchmarks—the practical bottleneck moves to solver engineering.
Beyond the paper: the multicore aspect is a real, if unquantified, part of the advantage; an open-source solver that uses all cores is arguably a fair comparison object for users, but a normalized rerun would separate model quality from hardware allocation.
Beyond the paper: the same MILP-plus-generic-solver pattern likely transfers to knapsack variants such as multiple knapsacks or additional side constraints, where no bespoke algorithm exists.
Beyond the paper: the sparse-graph regime is a testable boundary; running CP-SAT against the ILP baseline on densities 0.005–0.02 with larger capacities would map where the crossover actually sits.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: this is a legitimate empirical result, not a modeling breakthrough. The paper takes the MILP from [3], feeds it to CP-SAT, and shows that on the standard dense benchmark set it solves all 4,320 instances to optimality, with average times of 1.3 s, against published numbers of 4.8 s (CFS), 8.2 s (BCM), and 54.6 s (ILP). On the sparse set it is mostly competitive but visibly worse than ILP at densities 0.02 and 0.05 on large instances. That is the actual paper, and the abstract's 'comparable with, and often better than' is roughly accurate.

What earns credit: the experiments are clearly described, the comparison targets independent published algorithms, the formulation is correctly credited to [3], and there are no fitted parameters or invented benchmark instances. The authors also state the hardware/core-count disadvantage of the baselines, which is more than many short computational papers do.

The soft spot is exactly that hardware/core-count asymmetry. Baselines were single-core on a Xeon E5-2690; CP-SAT ran on all cores of an i7-12700F. The paper says the advantage 'will not change the outcome of the general experiments' without providing reruns or a sensitivity analysis. That is unquantified. No code or instance generator is provided either, so an external reader cannot check it. For the dense set the margins are large enough that I think the top-line claim survives—CP-SAT often solves in seconds what the baselines cannot solve in 600 s. For the sparse set, CP-SAT is already behind ILP in some rows, so equal resources could make it look worse, but the paper already concedes that region. So the load-bearing weakness is real but moderate, not fatal.

One small note on framing: 'state-of-the-art' here means the 2017 and 2021 published results, not necessarily the fastest current solver; that is a fair benchmark but should be stated. My overall take: the paper is useful, honest, and likely correct in its main direction. It deserves peer review, with the request that the authors rerun the baselines on the same machine or normalize thread counts, and release code/data. I would cite it if I worked on KPC or on fair solver benchmarking.

Referee Report

2 major / 5 minor

Summary. The paper studies the Knapsack Problem with Conflicts (KPC), a 0-1 linear program with a knapsack constraint and pairwise conflict constraints. It solves the previously known MILP formulation (Section III, equations (1)-(4)) using the open-source CP-SAT solver from Google OR-Tools. The authors compare CP-SAT against three published methods (CFS, BCM, and ILP/CPLEX) on two benchmark sets from the literature: a first set of 4,320 instances with conflict-graph densities 0.1-0.9 and various capacity/profit types, and a second set of 480 instances with very sparse conflict graphs (densities 0.001-0.05). On the first set, CP-SAT solves all 4,320 instances to optimality, often with lower average times than the published baselines. On the second set, CP-SAT is competitive but slightly inferior to the ILP approach. The paper concludes that the proposed approach achieves results comparable with, and often better than, state-of-the-art solvers, despite its conceptual simplicity.

Significance. If the empirical claims hold, the paper demonstrates that a generic, open-source MILP solver with no problem-specific tuning can outperform specialized branch-and-bound algorithms on dense KPC instances. The experimental campaign is extensive (4,800 instances total), the approach has no fitted parameters (only the time limit and thread count are free), and the reported optimality results on the first benchmark set are strong: CP-SAT proves optimality for all instances in every class, with average times from 0.0 to 14.5 seconds. This provides a useful, simple baseline for the KPC literature. The paper does not introduce new theory or algorithms, but the practical value of identifying that a stock constraint solver is competitive with purpose-built exact methods is real. The main weakness is that the comparison is not fully controlled for hardware and parallelism, which affects the strength of the headline claim.

major comments (2)

[IV-B] The comparison of CP-SAT with CFS, BCM, and ILP is not controlled for hardware and thread count. The paper states that the published baselines ran on a single core of an Intel Xeon E5-2690 (about 10% slower than the authors' Intel Core i7-12700F), while CP-SAT was allowed to use all cores. The paper then asserts, without any measurement or sensitivity analysis, that 'this will not change the outcome of the general experiments.' Because the headline metrics are wall-clock time and a 600-second timeout, the parallel solver receives a larger effective computational budget on every instance. This is load-bearing for the claim of 'often better' in the Abstract and Section V. I request either (i) rerunning CFS, BCM, and ILP on the same machine with the same single-core or multi-core configuration, (ii) running CP-SAT in single-core mode on the same hardware, or (iii) providing a quantitative adjustment (e.g., scaling factors) that supports the stated assertion. Without one of these, the central empirical claim is not yet established at the claimed strength.
[IV-B] The paper does not provide the instance generator, the exact instance files, or raw results, and it does not rerun the reference solvers on the same machine. Since the comparison relies on published timings from [10], an external reader cannot verify whether the observed speed advantage is due to CP-SAT's algorithm, the faster hardware, or the added parallelism. The lack of reproducibility is particularly problematic given the uncontrolled comparison noted above. The authors should make the instances and solver configuration available, and ideally also provide a script that runs the baseline methods on the same machine. This is not a request for new theory, but for the evidence needed to support the central empirical claim.

minor comments (5)

[Eq. (4)] In constraint (4), the index 'j ∈ V' should be 'i ∈ V'; the variable is x_i.
[Section I and IV-B] There are several typos: 'Knapack Problem' in the organization paragraph of Section I, 'an a machine' in Section IV-B, and 'data are aggregated' (repeated in table captions) should be 'data are aggregated' with a singular verb or 'data are aggregated' is acceptable but 'data is' is more common in this context.
[Tables III-IV] For CP-SAT, the 'Gap %' column and 'Sec' column should clarify whether the reported gap and time are averaged over all instances in the group or only over those solved to optimality; the baselines report times only for solved instances, so the comparison basis should be explicit.
[Section IV-B] The sentence 'All the instances are solved to optimality and with average computation times orders of magnitude smaller than those of the other solvers' is an overstatement. The overall averages in Table I show CP-SAT at 1.3 seconds versus CFS at 4.8 seconds, a factor of about 3.7, not 'orders of magnitude.' The claim should be moderated to reflect the actual margins.
[Conclusion] The statement 'for extreme cases such as densities such as 0.02 and 0.05' is redundant; consider 'for extreme low densities such as 0.02 and 0.05'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper solves a previously published MILP with CP-SAT and compares against independent literature baselines.

full rationale

The paper contains no derivation chain in which an output is equivalent to an input by construction. The model in Section III (Equations 1-4) is explicitly a previously known mixed integer linear program, and CP-SAT is used as an external solver on that model. The central empirical claim rests on Tables I-IV, where CP-SAT is compared with CFS, BCM, and ILP, all of which are algorithms from the independent literature ([10] and [3]). No parameter is fitted to the benchmark data and then renamed a prediction; no quantity is defined in terms of the quantity it is claimed to explain; and no uniqueness theorem or ansatz is imported from the authors' prior work. The only self-citations are [12]-[14], which motivate the choice of CP-SAT as a solver and are not load-bearing inputs to the experimental result. The acknowledged hardware and core-count asymmetry in Section IV-B is a genuine experimental-control limitation, but it is a correctness and reproducibility concern, not a circularity: an unfair comparison can make a claim unsupported, but it does not make the claim definitionally forced by its own inputs. Accordingly, no circular steps are present and the score is 0.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central claim is an empirical performance comparison, so the relevant 'free parameters' are experimental configuration choices (time limit, parallelism) plus the untested assumption that published baseline timings are comparable. There are no fitted constants in the MILP itself, and no invented entities.

free parameters (2)

Time limit = 600 seconds
Maximum runtime allowed per instance for all solvers; chosen as in [10], not fitted to data, but average times and solved counts depend on it.
Thread count / parallelism = not specified (CP-SAT uses all cores)
CP-SAT is run with all processor cores while baselines were single-core; this configuration gives CP-SAT a runtime advantage and is a key uncontrolled factor in the comparison.

assumptions (3)

domain assumption The published baseline timings in [10] are accurate and directly comparable despite different hardware and single-core execution.
The paper's comparison rests on accepting the baseline numbers and the authors' assertion that the hardware and parallelism advantage does not change the outcome.
domain assumption The benchmark instances from [3] accurately represent KPC difficulty and are used without modification.
The conclusions are about these instances; representativeness is assumed from the literature.
standard math CP-SAT correctly solves the MILP to proven optimality when it reports optimal.
This trusts the open-source solver's correctness for mixed-integer linear programming, a standard assumption in computational studies.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On Solving the Knapsack Problem with Conflicts." pith.science (2026). https://pith.science/paper/3SF75AGJ

@misc{pith2026250603330,
  author       = {Pith},
  title        = {Pith review of: On Solving the Knapsack Problem with Conflicts},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3SF75AGJ}},
  note         = {Machine review of arXiv:2506.03330}
}

read the original abstract

A variant of the well-known Knapsack Problem is studied in this paper, where pairs of items are conflicting, and cannot be selected at the same time. This configures a set of hard constraints. The problem, which can be used to model real applications, looks for a selection of items such that the total profit is maximized, the capacity of the container is respected, and no conflict is violated. In this paper, we consider a previously known mixed integer linear program representing the problem and we solve it with the open-source solver CP-SAT, part of the Google OR-Tools computational suite. An experimental campaign on the instances available from the literature and adopted in the last decade, indicate that the approach we propose achieves results comparable with, and often better than, those of state-of-the-art solvers, notwithstanding its intrinsic conceptual and implementation simplicity.

Figures

Figures reproduced from arXiv: 2506.03330 by the authors.

**Figure 1.** On the left an example of a KPC instance is presented, where for each item the profit is indicated in red and the weight [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

16 extracted references · 10 canonical work pages

[3]

A branch-and-bound algorithm for the knapsack problem with conflict graph,

A. Bettinelli, V . Cacchiani, and E. Malaguti, “A branch-and-bound algorithm for the knapsack problem with conflict graph,” INFORMS Journal on Computing , vol. 29, no. 3, pp. 457–473, 2017

2017
[10]

A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts,

S. Coniglio, F. Furini, and P. San Segundo, “A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts,” European Journal of Operational Research, vol. 289, no. 2, pp. 435–455, 2021

2021
[1]

Martello and P

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

work page 1990
[2]

A new branch-and-price-and- cut algorithm for one-dimensional bin-packing problems,

L. Wei, Z. Luo, R. Baldacci, and A. Lim, “A new branch-and-price-and- cut algorithm for one-dimensional bin-packing problems,” INFORMS Journal on Computing , vol. 32, no. 3, pp. 428–443, 2019

work page 2019
[4]

Heuristic and exact algo- rithms for the disjunctively constrained knapsack problem,

T. Yamada, S. Kataoka, and K. Watanabe, “Heuristic and exact algo- rithms for the disjunctively constrained knapsack problem,” INFORMS Journal on Computing , vol. 43, no. 9, pp. 2864–2870, 2002

work page 2002
[5]

Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem,

M. Hifi and M. Michrafy, “Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem,” Computers & Operations Research, vol. 34, no. 9, pp. 2657–2673, 2007

work page 2007
[6]

A reactive local search-based algorithm for the disjunctively constrained knapsack problem,

——, “A reactive local search-based algorithm for the disjunctively constrained knapsack problem,” Journal of the Operational Research Society, vol. 57, no. 6, pp. 718–726, 2006

work page 2006
[7]

Local branching- based algorithms for the disjunctively constrained knapsack problem,

H. Akeb, M. Hifi, and M. E. Ould Ahmed Mounir, “Local branching- based algorithms for the disjunctively constrained knapsack problem,” Computers & Industrial Engineering , vol. 60, no. 4, pp. 811–820, 2011

work page 2011

Show all 16 references

[8]

An algorithm for the disjunctively constrained knapsack problem,

M. Hifi and N. Omani, “An algorithm for the disjunctively constrained knapsack problem,” International Journal of the Operational Research , vol. 13, no. 1, pp. 22–43, 2012

2012
[9]

An iterative rounding search-based algorithm for the dis- junctively constrained knapsack problem,

M. Hifi, “An iterative rounding search-based algorithm for the dis- junctively constrained knapsack problem,” Engineering Optimization , vol. 46, no. 8, pp. 1109–1122, 2014

2014
[11]

Google OR-Tools - CP-SAT,

L. Perron and F. Didier, “Google OR-Tools - CP-SAT,” Google, 2025, https://developers.google.com/optimization/cp/cp solver/

2025
[12]

Solving the parallel drone schedul- ing traveling salesman problem via constraint programming,

R. Montemanni and M. Dell’Amico, “Solving the parallel drone schedul- ing traveling salesman problem via constraint programming,” Algo- rithms, vol. 16, no. 1, p. 40, 2023

2023
[13]

Parallel drone scheduling vehicle routing problems with collective drones,

R. Montemanni, M. Dell’Amico, and A. Corsini, “Parallel drone scheduling vehicle routing problems with collective drones,” Computers & Operations Research , vol. 163, p. 106514, 2024

2024
[14]

Solving a home healthcare routing and scheduling problem with real-world features,

R. Montemanni, “Solving a home healthcare routing and scheduling problem with real-world features,” in Proceedings of the 9th Interna- tional Conference on Machine Learning and Soft Computing . Springer, to appear, 2025

2025
[15]

A hybrid grouping genetic algorithm for bin packing,

E. Falkenauer, “A hybrid grouping genetic algorithm for bin packing,” Journal of Heuristics , vol. 2, pp. 5–30, 1996

1996
[16]

IBM CPLEX Optimizer,

IBM, “IBM CPLEX Optimizer,” 2024, https://www.ibm.com/de-de/ analytics/cplex-optimizer [Accessed: 2024-03-14]. TABLE III: Results on the set benchmark set of correlated instances (aggregated by number of Items/Capacity and Density) Instances CFS [10] BCM [3] ILP [10] CP-SAT It...

2024

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [3]

A branch-and-bound algorithm for the knapsack problem with conflict graph,

A. Bettinelli, V . Cacchiani, and E. Malaguti, “A branch-and-bound algorithm for the knapsack problem with conflict graph,” INFORMS Journal on Computing , vol. 29, no. 3, pp. 457–473, 2017

2017

[2] [10]

A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts,

S. Coniglio, F. Furini, and P. San Segundo, “A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts,” European Journal of Operational Research, vol. 289, no. 2, pp. 435–455, 2021

2021

[3] [1]

Martello and P

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

work page 1990

[4] [2]

A new branch-and-price-and- cut algorithm for one-dimensional bin-packing problems,

L. Wei, Z. Luo, R. Baldacci, and A. Lim, “A new branch-and-price-and- cut algorithm for one-dimensional bin-packing problems,” INFORMS Journal on Computing , vol. 32, no. 3, pp. 428–443, 2019

work page 2019

[5] [4]

Heuristic and exact algo- rithms for the disjunctively constrained knapsack problem,

T. Yamada, S. Kataoka, and K. Watanabe, “Heuristic and exact algo- rithms for the disjunctively constrained knapsack problem,” INFORMS Journal on Computing , vol. 43, no. 9, pp. 2864–2870, 2002

work page 2002

[6] [5]

Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem,

M. Hifi and M. Michrafy, “Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem,” Computers & Operations Research, vol. 34, no. 9, pp. 2657–2673, 2007

work page 2007

[7] [6]

A reactive local search-based algorithm for the disjunctively constrained knapsack problem,

——, “A reactive local search-based algorithm for the disjunctively constrained knapsack problem,” Journal of the Operational Research Society, vol. 57, no. 6, pp. 718–726, 2006

work page 2006

[8] [7]

Local branching- based algorithms for the disjunctively constrained knapsack problem,

H. Akeb, M. Hifi, and M. E. Ould Ahmed Mounir, “Local branching- based algorithms for the disjunctively constrained knapsack problem,” Computers & Industrial Engineering , vol. 60, no. 4, pp. 811–820, 2011

work page 2011