{"id":"7f4b7dd3-04f0-461b-9758-02420955a4b7","arxiv_id":"2506.04274","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Solving the known MILP for the Assignment Problem with Conflicts with Google's open-source CP-SAT solver matches or beats specialized exact and heuristic methods on literature benchmarks.","lead":"The authors apply Google's free CP-SAT solver to a previously known optimization model for the Assignment Problem with Conflicts, a matching problem with forbidden pairs. On standard benchmarks it matches dedicated algorithms and often beats the commercial solver, suggesting that a simple, open-source setup can replace specialized methods.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Cross-machine runtime comparison is the load-bearing weakness: without same-hardware reruns or a reliable CPU speed ratio, CP-SAT's 'comparable' exact times and 'quicker and better' heuristic claim do not follow from Table I.","rationale":"The reader correctly identified the cross-machine runtime comparison as the weakest assumption. My reading agrees with that, but I would sharpen it: the paper's own speed estimate, when actually applied, makes CP-SAT's exact times about three times worse than BIP/B&B, so the 'comparable' language in the abstract is not merely unproven but likely false under the paper's own correction. I also find a second, independent issue in the heuristic claim: Table I shows LS is far quicker than CP-SAT in finding a best solution, so the abstract's 'quicker and better' is internally contradicted by the paper's data. This is not a mathematical error in the MILP formulation, but an empirical benchmarking weakness. The appropriate remedy is a rerun on common hardware and a revision of the abstract and conclusions to match the table. These are addressable, so the paper should not be rejected outright, but it should not be accepted as-is. The reader's conditional verdict is therefore appropriate, and the specific conditions should include same-machine comparisons and corrected claims.","tokens_in":6202,"tokens_out":6549,"duration_ms":74351,"concrete_test":"Rerun LS, RDS, BIP, and B&B from [3] on the same Intel Core i7-12700F machine used for CP-SAT, with the same 3600-second time limit and the same recorded metrics (Sec Best, Sec Opt, Gap), on all 130 usable instances plus the five excluded ones. Then recompute the reported averages and per-instance win counts. If, after same-machine comparison or after applying a measured CPU speed ratio, CP-SAT's Sec Opt is not within a factor of two of BIP on a majority of instance groups, the abstract's 'comparable' claim should be weakened to 'competitive on some instance classes.' Separately, run CP-SAT as a heuristic with a time limit equal to LS's Sec Best on each instance and compare the resulting gaps to LS's reported gaps; this directly tests the 'quicker and better' heuristic claim.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's central claim that CP-SAT is competitive with LS, RDS, BIP, and B&B rests on comparing Table I against published runtimes from [3], measured on a different CPU. The only correction is an estimate from a website that the old CPU is '3 or more times slower.' Applying that factor to the exact-solver averages makes CP-SAT's Sec Opt roughly 204.5×3 ≈ 613 seconds on the old machine, versus BIP at 194.1 and B&B at 216.5; CP-SAT is then about three times slower, not comparable. If the speed ratio is inaccurate, the comparison is unquantified. For the heuristic claim, the abstract says CP-SAT provides solutions 'quicker and better' than previous heuristics, but Table I contradicts this for LS: LS's average Sec Best is 6.6 seconds versus CP-SAT's 141.6 seconds, so CP-SAT is about 21 times slower at finding a best solution, although it achieves a better average gap (0% vs. 3.08%). The table only supports 'better gap than LS and RDS' and 'faster on average than RDS,' not 'quicker than LS.' Additionally, the five excluded instances are not documented, leaving open the possibility that the averages are affected by selective exclusion.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Assignment Problem with Conflicts (APC), an assignment problem variant with pairwise conflict constraints. The authors take the previously known MILP formulation (1)-(5), solve it with the open-source CP-SAT solver (OR-Tools 9.12), and compare it against four published methods (LS, RDS, BIP, B&B) on the benchmark set from [3]. Experiments are reported for 130 of the 135 available instances, with average gaps and runtimes in Table I. The paper concludes that CP-SAT achieves results comparable to the exact state-of-the-art methods, and that it provides heuristic solutions that are \"quicker and better\" than the previously proposed heuristics.","tokens_in":6481,"tokens_out":4002,"duration_ms":43616,"significance":"If the empirical claims are correct, the paper provides a useful practical data point: a generic, open-source CP-SAT solver can match or even outperform dedicated algorithms on a standard APC benchmark with minimal implementation effort. The experimental results are transparently tabulated, and the authors correctly acknowledge the hardware-speed caveat, which is more than many empirical papers do. However, the significance is conditional on resolving the cross-machine runtime comparability and on documenting the five excluded instances; without those, the central \"comparable\" claim is not yet established. The paper does not introduce new theory or algorithms, so its value is empirical and comparative.","major_comments":[{"comment":"The runtime comparison across machines is not quantitatively reliable. The only adjustment for the hardware difference is an informal web-derived estimate that the older CPU is \"3 or more times slower.\" Applying this factor to the average Sec Opt values gives CP-SAT approximately 613 seconds versus 194.1 seconds for BIP and 216.5 seconds for B&B, which would make CP-SAT about three times slower rather than comparable. The authors should either rerun the compared methods on the same hardware, or provide a justified and sensitivity-tested performance normalization, before claiming that the exact times are comparable.","section":"Section IV-B, Table I"},{"comment":"The statement that CP-SAT provides heuristic solutions \"quicker and better\" than prior heuristics is contradicted by Table I for the LS heuristic: the average Sec Best is 6.6 seconds for LS versus 141.6 seconds for CP-SAT. The data support the claims that CP-SAT achieves a better average gap (0% versus 3.08%) and is faster on average than RDS (141.6 seconds versus 566.4 seconds), but they do not support the \"quicker\" claim with respect to LS. Please revise the claim or add experiments with CP-SAT under time limits comparable to LS so that the speed assertion is substantiated.","section":"Abstract and Section V"},{"comment":"The five excluded instances are not documented. The benchmark originally contains 135 instances and the paper uses 130, citing \"some inconsistencies in the available dataset,\" but gives no information about which instances were removed or what the inconsistencies were. Because the averages in Table I are computed over the remaining 130 instances, the reader cannot assess whether the exclusions affect the conclusions. Please list the excluded instances (e.g., by |VA| and |C|), describe the inconsistencies, and preferably show that the reported averages are robust to their removal or report results for the full set.","section":"Section IV-A"}],"minor_comments":[{"comment":"The phrase \"comparable with, those of state-of-the-art solvers\" contains a stray comma; it should read \"comparable with those of state-of-the-art solvers.\"","section":"Abstract"},{"comment":"The definition of the conflict set C is written as \"C = {{i, j}, {k, l} | {{i, j}, {k, l}} ∈ E}\", which is not a standard set-builder notation for a set of unordered pairs of edges. Please define C precisely as a set of two-element subsets of E.","section":"Section II"},{"comment":"Table I does not report a Gap% column for CP-SAT, even though the text claims that CP-SAT finds optimal solutions for all instances. Adding a Gap% column for CP-SAT would allow the reader to verify this claim directly from the table.","section":"Section IV-B"},{"comment":"The hardware-speed ratio is currently supported only by a URL reference. It would be more rigorous to cite a specific benchmark or provide the CPU models and a measured or well-known speed ratio, rather than relying on an informal web page.","section":"Section IV-B"},{"comment":"Reference [16] lists an author as \"G. Schauer, J.and Woeginger\"; this appears to be a formatting error and should be corrected to \"J. Schauer and G. J. Woeginger\" (or the appropriate author list).","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The paper's contribution is largely empirical: the MILP formulation is directly taken from [3], and the use of CP-SAT is not novel. If the journal's scope emphasizes algorithmic novelty, the paper may be marginal; if computational studies are acceptable, the paper could be suitable after the runtime-comparison issue is resolved. The heavy self-citation of [21]-[23] only motivates the solver choice and does not affect the technical content. The central weakness is the cross-machine time comparison, which needs to be either removed or properly justified."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a small, honest benchmark paper. The genuinely new content is one run: CP-SAT 9.12 on the 130 usable APC instances from Öncan et al. 2019, using the same MILP that was already in that paper. No new model, algorithm, or theorem. What the paper does well: the formulation is correctly transcribed, the experimental table is detailed enough to see per-instance-group behavior, and the final discussion is measured — it actually says BIP is often the best option and CP-SAT sits in between. That is more balanced than the abstract.\n\nSoft spots, in proportion. The big one is the baseline comparison. CP-SAT ran on an i7-12700F; LS/RDS/BIP/B&B times come from [3] on an older 2.2 GHz i7, with the speed ratio only a web-site estimate ('3 or more times slower'). The stress-test note is right: if you apply the 3x correction, CP-SAT's average Sec Opt (204.5s) becomes ~613s on the old machine, which is worse than BIP's 194.1 and B&B's 216.5, not comparable. The paper's own conclusion already downgrades CP-SAT to 'in between,' so the exact-solver claim mostly survives in spirit, but the abstract's 'comparable with state-of-the-art solvers' is too strong without same-hardware reruns or a better-calibrated CPU ratio.\n\nThe heuristic claim is the clearest overreach. The abstract says CP-SAT provides heuristic solutions 'quicker and better' than prior heuristics. Table I shows CP-SAT Sec Best 141.6s on average vs LS 6.6s — 21x slower. CP-SAT is better on gap (0% vs 3.08%) and faster than RDS on average, so the abstract should say 'better' and, against RDS only, 'quicker.' That is an easy fix.\n\nAlso minor: five of the 135 instances are dropped for 'inconsistencies' but never listed. That is opaque; a table or footnote of which instances and what the inconsistency was would close the question of selective exclusion. The self-citations [21]-[23] are just motivation and don't do any load-bearing work — not a problem.\n\nVerdict: this deserves a serious referee. The experimental comparison is reproducible in principle (open-source solver, public benchmark), the model is correct, and the paper is honest enough in its main conclusions. A revision that fixes the heuristic wording, either reruns baselines or narrows the performance claims to what the hardware correction supports, and documents the excluded instances would make it a sound little contribution. For an APC practitioner deciding between CP-SAT and custom code, the table is useful even with the cross-machine caveat.","headline":"A small, honest benchmark paper: the new result is CP-SAT 9.12 on existing APC instances, but the abstract overstates the heuristic gains and the cross-machine CPU comparison weakens the exact-solver claim.","tokens_in":6992,"tokens_out":1853,"would_cite":false,"duration_ms":18892,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C10","90C27","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"A general-purpose solver matches specialized algorithms on the assignment problem with conflicts.","keywords":["assignment problem with conflicts","perfect matching","conflict constraints","mixed integer linear programming","CP-SAT","constraint programming","exact algorithms","heuristics"],"falsifier":"Re-run the LS, RDS, BIP, and B&B implementations on the same CPU as CP-SAT with identical 3600-second limits and compare time-to-best and time-to-proof on the 130 instances; if CP-SAT's advantage over RDS disappears or its proof times exceed BIP's by a large margin, the central claim would fail.","tokens_in":6014,"feed_emoji":"🧩","tokens_out":7691,"duration_ms":83051,"temperature":0.7,"pith_summary":"The paper aims to show that a previously known mixed integer linear program for the Assignment Problem with Conflicts—the problem of finding a cheapest perfect matching in a bipartite graph under constraints that forbid certain pairs of assignments from being chosen together—can be solved just as effectively by a general-purpose open-source constraint solver as by the purpose-built algorithms in the literature. The authors take the previously known model, write it in a few lines, and hand it to the CP-SAT solver without any custom search logic. On the 130 usable benchmark instances from the reference work, the solver finds the same optimal values that the dedicated exact methods find, and when used as a heuristic it returns optimal solutions faster than the dedicated Russian-doll-search heuristic and with a smaller gap than local search. The practical message is that a practitioner facing this problem need not implement specialized machinery to obtain good exact or heuristic solutions.","feed_headline":"Open-source solver matches specialist assignment algorithms","feed_subtitle":"Feeding a standard integer program to one general solver ties the dedicated exact methods and beats the heuristics.","key_machinery":"The central vehicle is the previously known integer program (1)–(5). For each possible assignment between a left node $i$ and a right node $j$, a binary variable $x_{ij}$ is either 1 (selected) or 0; constraints (2) and (3) force each node to be matched exactly once, and each conflicting pair $\\{i,j\\},\\{k,l\\}$ contributes the inequality $x_{ij}+x_{kl}\\le 1$, which forbids selecting both. The other half of the machinery is the CP-SAT solver run as a black box: the paper applies no branching rule, no cutting planes, and no heuristic of its own, so the result is a statement about how much can be achieved with a general solver alone.","core_discovery":"On its own terms, the paper claims that CP-SAT, solving the model (1)–(5) with binary assignment variables $x_{ij}$, assignment equalities (2)–(3), and one inequality $x_{ij}+x_{kl}\\le 1$ per conflict, reaches all optimal values on the 130 usable benchmark instances. In the exact comparison, average time to proof is 204.5 seconds, against 194.1 for BIP and 216.5 for B&B; the differences are small, and the paper notes BIP remains the most robust option overall and B&B the best on the largest instances. In the heuristic comparison, CP-SAT's average gap is zero (it finds every optimum), whereas RDS leaves an average gap of 0.02% and local search 3.08%, and CP-SAT's average time to best solution is 141.6 seconds versus 566.4 for RDS. The paper therefore establishes that a conceptually simple, off-the-shelf formulation can compete with dedicated algorithms on this benchmark.","pith_inferences":["The runtimes of the earlier methods were measured on a machine the authors estimate is at least three times slower; if that factor differs, CP-SAT's speed advantage over RDS and its parity with BIP and B&B would change.","Because the method is generic, the same model should extend to thicker conflict structures, such as triple conflicts or conflicts with weights, without new algorithmic work.","The largest instance in the benchmark has 500 nodes and 200,000 conflicts; testing beyond this conflict density would reveal where a generic solver's performance degrades relative to the specialized methods."],"forward_implications":["CP-SAT proves optimality on all 130 usable benchmark instances, matching the dedicated exact methods BIP and B&B.","As a heuristic, CP-SAT finds every optimum on these instances, with zero average gap, versus 0.02% for RDS and 3.08% for local search.","CP-SAT's average time to best solution is about a quarter of RDS's (141.6 seconds versus 566.4 seconds) on comparable hardware.","For small and medium instances, BIP still gives proven optima faster, while B&B wins on the largest instances; CP-SAT occupies the balanced middle.","No custom algorithm is required: the entire method is a standard model plus a general solver."],"supporting_citations":[{"why":"Provides the benchmark instances, the previously known MILP model, and the LS, RDS, BIP, and B&B results that CP-SAT is compared against.","marker":"[3]"},{"why":"The open-source CP-SAT solver whose default behaviour is the method under test.","marker":"[20]"},{"why":"Introduces the MILP model and exact/heuristic ideas that the reference work summarizes.","marker":"[18]"},{"why":"Presents the branch-and-bound approach and heuristics that [3] extends.","marker":"[19]"},{"why":"The commercial solver used in the BIP comparison baseline.","marker":"[24]"}],"fun_headline_variants":["Simple CP-SAT ties specialized solvers on conflicted assignments","Off-the-shelf OR-Tools solver rivals bespoke algorithms for assignment","Generic solver matches exact methods on conflict-constrained assignment","Open-source CP-SAT beats heuristic gap but ties exact solvers"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper's performance conclusions treat the earlier methods' published runtimes as directly comparable to the new runtimes even though they were produced on a machine estimated to be at least three times slower; if that estimate is wrong, the claimed parity and speed advantage shift.","fun_headline_variants_meta":{"raw":{"variants":["Simple CP-SAT ties specialized solvers on conflicted assignments","Off-the-shelf OR-Tools solver rivals bespoke algorithms for assignment","Generic solver matches exact methods on conflict-constrained assignment","Open-source CP-SAT beats heuristic gap but ties exact solvers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000551,"raw_usage":{"total_tokens":2596,"prompt_tokens":883,"completion_tokens":1713,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":499,"completion_tokens_details":{"reasoning_tokens":1641}},"tokens_in":499,"tokens_out":1713,"duration_ms":14199,"temperature":1.0,"reasoning_tokens":1641,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:05:07.443314+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-run the LS, RDS, BIP, and B&B implementations on the same CPU as CP-SAT with identical 3600-second limits and compare time-to-best and time-to-proof on the 130 instances; if CP-SAT's advantage over RDS disappears or its proof times exceed BIP's by a large margin, the central claim would fail.","supporting_citations":[{"cited_title":"Assignment problem with conflicts,","cited_arxiv_id":null,"evidence_quote":"Provides the benchmark instances, the previously known MILP model, and the LS, RDS, BIP, and B&B results that CP-SAT is compared against."},{"cited_title":"Google OR-Tools - CP-SAT,","cited_arxiv_id":null,"evidence_quote":"The open-source CP-SAT solver whose default behaviour is the method under test."},{"cited_title":"Iterated exact and heuristic algorithms for the minimum cost bipartite perfect matching problem with conflict constraints,","cited_arxiv_id":null,"evidence_quote":"Introduces the MILP model and exact/heuristic ideas that the reference work summarizes."},{"cited_title":"A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints,","cited_arxiv_id":null,"evidence_quote":"Presents the branch-and-bound approach and heuristics that [3] extends."},{"cited_title":"IBM CPLEX Optimizer,","cited_arxiv_id":null,"evidence_quote":"The commercial solver used in the BIP comparison baseline."}],"review_version":1}