{"id":"df5d4137-2f53-4cad-9472-a90ca9da3c33","arxiv_id":"2501.03390","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"SCIP-based solvers won five of six categories in the 2024 Pseudo-Boolean competition, and post-competition enhancements raised SCIP's solved instances from 760 to 782 while reducing average time by 9%.","lead":"This paper reports that SCIP and FiberSCIP, open-source optimization solvers, won five of six categories in the 2024 Pseudo-Boolean competition, solving 759 and 776 of 1,207 instances respectively, and presents the algorithmic features behind the wins. It matters because it shows a general integer-programming framework can match dedicated pseudo-Boolean solvers by adding PB-specific cuts, symmetry handling, and conflict analysis.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Table 4 cannot support the attribution of SCIP's PB24 success to the new cut families: RLT and flower inequalities affect only 14 and 3 instances, with no statistical evidence.","rationale":"The reader's weakest assumption identifies exactly the point I would stress. The paper's factual contribution is solid: the PB24 competition results are reported from the official scoreboard, and the existence of SCIP and FiberSCIP as competitive pseudo-Boolean solvers is not in question. But the explanatory narrative, namely that the newly described algorithmic ideas are what makes SCIP state-of-the-art, depends on the ablations in Table 4, and that table is too thin to carry the claim. RLT cuts and flower inequalities touch 14 and 3 instances respectively and produce zero change in solved-instance counts; a 40% time ratio computed from three instances is not statistically distinguishable from noise. This is not an accusation of dishonesty; it is an observation about evidential strength. The proposed held-out, seeded, paired comparison would settle whether the effects reproduce, and until then the conditional verdict is appropriate: accept the competition facts, but withhold full confidence in the causal attribution of the wins to the specific features.","tokens_in":13030,"tokens_out":8439,"duration_ms":81360,"concrete_test":"Re-run the four ablations of Table 4 on PB16/PB22 instances, or on a random 70/30 split of the PB24 benchmark, using at least five random seeds per configuration and recording per-instance solving times; then compute paired Wilcoxon signed-rank tests on the affected-instance time ratios and bootstrap confidence intervals for the change in solved counts. If RLT cuts and flower inequalities do not show a statistically significant effect at p<0.05 and do not change solved counts on the held-out set, the paper should downgrade the claim from 'winning algorithmic ideas' to 'instance-specific gains'.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The competition scoreboard in Tables 2 and 3 is a verifiable fact and is not the weak point. The load-bearing step is the causal reading in Section 3.4: the post-competition improvement, credited to cut-based conflict analysis and symmetry handling, and the abstract's 'winning algorithmic ideas', including RLT cuts and flower inequalities, rest entirely on Table 4. There, disabling RLT cuts affects only 14 instances and changes the solved count by 0; disabling flower inequalities affects only 3 instances and also changes the solved count by 0. The reported speedups (1.26x and 1.40x on affected instances) are presented without per-instance times, confidence intervals, or any correction for the fact that these features were developed and tuned on the same 1,207-instance PB24 benchmark used for evaluation. With n=3, a single instance-level anomaly can dominate the quotient, so the data are consistent with noise or with feature interactions rather than with a robust causal effect. Symmetry handling and cut-based conflict analysis rest on larger affected sets, but they are still in-sample aggregate ratios, and the comp/post-comp comparison lacks a commit hash and exact parameter file, making independent reproduction impossible.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper reports on SCIP and FiberSCIP's participation in the 2024 Pseudo-Boolean competition, in which solvers using the SCIP framework won five of six categories, with SCIP solving 759 and FiberSCIP 776 of 1,207 instances. It describes algorithmic features added or modified for pseudo-Boolean solving: RLT cuts for AND constraints, flower inequalities for multilinear constraints, symmetry handling, numerical feasibility handling, large-integer heuristics, and post-competition cut-based conflict analysis. The paper also presents a post-competition comparison showing that an updated SCIP version solves 782 instances versus 760 for the competition version, with a 9% reduction in geometric mean time, and an ablation study in Table 4 attributing gains to individual features.","tokens_in":13241,"tokens_out":6449,"duration_ms":53362,"significance":"The competition results are independently verified and establish SCIP as a top-performing pseudo-Boolean solver, which is a meaningful contribution. The paper provides a useful description of the solver's features and a reasonable single-machine comparison protocol for the post-competition version. However, the causal attribution of the performance to specific new cut families is not supported by the ablation evidence: RLT cuts and flower inequalities affect only 14 and 3 instances, respectively, with zero change in solved count, and the reported speedups have no per-instance detail or statistical analysis. The lack of exact version identifiers also hinders reproducibility. If the claims are tempered or the experiments are strengthened, the paper would be a valuable record of the competition and the solver's development.","major_comments":[{"comment":"The ablation study does not support the paper's causal reading that RLT cuts and flower inequalities are \"winning algorithmic ideas.\" Disabling RLT cuts affects only 14 instances and changes the solved count by 0; disabling flower inequalities affects only 3 instances and also changes the solved count by 0. The reported speedups (1.26x and 1.40x) are computed on post hoc defined \"affected\" instances, with no per-instance times, confidence intervals, or correction for the fact that these features were tuned on the same competition benchmark. With n=3, a single instance-level anomaly can dominate the quotient, so the data are consistent with noise or feature interactions. The same concern applies to the symmetry and cut-based conflict analysis ablations, which are presented as in-sample aggregate ratios without variance measures. Please provide instance-level detail and statistical analysis, or temper the claims in the abstract and in Sections 2.1 and 2.2.","section":"Section 3.4, Table 4"},{"comment":"The comparison between comp. Scip and post-comp. Scip is not reproducible from the information given. The paper does not provide a commit hash, version number, or exact parameter file for either solver configuration. Since the claimed improvement (782 vs 760 solved instances, 9% geometric mean time reduction) is a central post-competition result, the authors should make the exact code versions and settings available, ideally as a public artifact or precise version identifiers.","section":"Section 3.4"}],"minor_comments":[{"comment":"The integer size distribution entries sum to 1216 (1126+77+9+4), not the stated total of 1,207 instances. Please correct the inconsistency and ensure that the distribution matches the competition totals used elsewhere.","section":"Table 1"},{"comment":"The phrase \"brand-and-bound tree\" should be \"branch-and-bound tree.\"","section":"Section 3.2"},{"comment":"The sentence \"As is evident from the analysis in the next section\" is confusing because Section 3.4 does not analyze Mixed-Bag's composition; please clarify or remove the cross-reference.","section":"Section 3.3"},{"comment":"The statement \"this exclusive upper bound is at least 2^s\" appears to be a typo; it should likely be \"at most 2^s\" (or \"less than 2^s\") for the subsequent argument that ǫ_f < 2^{-s} implies ǫ_f < 1/(||C||_1+1).","section":"Section 2.4"},{"comment":"The figure would benefit from a caption and a description of which solver version's running times are plotted; currently it is referenced in the text but not fully explained.","section":"Figure 1"},{"comment":"The abstract says \"solvers based on SCIP won five out of six categories\" and later refers to \"winning algorithmic ideas\"; please clarify that the competition wins include results achieved by other solvers that embed SCIP, and ensure the attributed ideas are those actually supported by the evidence.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The paper's competition results are solid and externally benchmarked, but the causal attribution of the performance to particular features is the load-bearing part of the narrative and is currently under-supported. The Table 1 sum inconsistency and the reproducibility gap in Section 3.4 should also be addressed. With these fixes, the paper could be acceptable; as is, a major revision is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: the competition results are the paper, and they hold up. SCIP and FiberSCIP won five of six PB24 categories, and the official scoreboard is an externally benchmarked fact, not a self-reported number. The post-competition improvement is also a genuine new result: re-running the old and new versions on the same machine gives 782 vs 760 solved and a 9% geometric-mean time reduction. That is worth taking seriously.\n\nWhat the paper does well: it is transparent about settings, machine configurations, and the distinction between competition hardware and the post-competition re-evaluation. The numerical-tolerance discussion is thoughtful, with a clean bound relating the absolute feasibility tolerance to the OPB intsize, and the large-integer heuristic modification is a sensible practical fix. The FiberSCIP glue code being only 57 lines is a nice data point for the UG framework.\n\nThe soft spot is exactly where the stress test points: Table 4. The attribution of SCIP's success to RLT cuts and flower inequalities rests on 14 and 3 affected instances, respectively, with zero change in solved count and no per-instance times, confidence intervals, or interaction analysis. Those two features are the headline 'winning algorithmic ideas' in the abstract, and the evidence for them is anecdote-level. The symmetry-handling and cut-based conflict-analysis rows are on larger affected sets (213 and 374) but are still in-sample aggregate ratios with no variance estimate. The paper also never gives a commit hash or parameter file, so the post-comp run is not independently reproducible. One more minor wrinkle: the competition version solved 759 instances at PB24, while the re-evaluated comp. Scip solves 760 on the newer machine; the paper doesn't explain that one-instance shift.\n\nNone of this undermines the competition outcome. But it does mean the explanatory claims in Section 3.4 and the abstract outrun the data. The fix is straightforward: add per-instance scatter/ratio data, report standard errors, and either soften the causal language or confirm the effects with a holdout set.\n\nWho is this for? People who care about the practical state of pseudo-Boolean solving, competition benchmarks, and SCIP's feature set. It deserves a serious referee, not a desk reject; the scores and implementation details are real and useful. I would ask for reproducibility artifacts and a more careful ablation in the referee report.","headline":"The PB24 scoreboard is real and the paper is a useful honest engineering report, but the ablation table is far too thin to support the claimed causal role of the new cut families.","tokens_in":13812,"tokens_out":1872,"would_cite":true,"duration_ms":20646,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C10","90C57","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"SCIP-based solvers win five of six pseudo-Boolean categories in the 2024 competition, with post-competition tuning pushing the sequential solver to 782 solved instances.","keywords":["Pseudo-Boolean","SCIP","integer programming","branch-and-cut","RLT cuts","flower inequalities","symmetry handling","conflict analysis"],"falsifier":"Run SCIP on a fresh, time-locked set of pseudo-Boolean instances (for example, the next competition's benchmark) with and without each feature individually, using a pre-registered definition of affected instances and a sample large enough for statistical testing; if disabling flower inequalities or RLT cuts no longer slows the solver on affected instances, the paper's attribution fails.","tokens_in":12836,"feed_emoji":"🧩","tokens_out":4811,"duration_ms":41269,"temperature":0.7,"pith_summary":"The paper reports that solvers built on the SCIP constraint-integer-programming framework won five of the six categories in the 2024 Pseudo-Boolean competition, solving 759 of 1,207 instances in the sequential version and 776 with the parallel FiberSCIP. It argues that this success comes from treating pseudo-Boolean problems as integer linear programs and applying a mature branch-and-cut engine, then extends the result with post-competition improvements that raise the sequential solver to 782 solved instances while cutting average runtime by 9 percent. The paper identifies symmetry handling, RLT cuts for AND constraints, flower inequalities, and cut-based conflict analysis as the main contributors. A fair reader should care because the result demonstrates that general-purpose integer-programming machinery can be state-of-the-art for a domain historically dominated by SAT-style solvers.","feed_headline":"SCIP-based solvers win five of six pseudo-Boolean categories","feed_subtitle":"Out of 1,207 competition instances, SCIP solved 759 and FiberSCIP 776; post-competition retuning solves 782.","key_machinery":"The load-bearing machinery is the SCIP branch-and-cut framework, which treats pseudo-Boolean problems as pure integer linear programs over binary variables after linearizing AND constraints. On top of that base, four additions carry the argument: RLT cuts generated for the bilinear terms hidden in AND constraints; k-flower inequalities (k=1,2) separated from the hypergraph of AND constraints in linear time; symmetry handling via detection graphs that find permutation and reflection symmetries, with orbitopal fixing and lexicographic constraints; and cut-based conflict analysis that interprets conflicts as linear combinations, roundings, and cuts. A numerical pre-check that rounds floating-point candidate solutions before evaluating feasibility ensures exactness for large-coefficient constraints.","core_discovery":"The central claim is that SCIP, an open-source constraint integer programming solver, is currently a state-of-the-art pseudo-Boolean solver, and that its edge comes from combining LP-based branch-and-cut with domain-specific additions. In the 2024 competition, SCIP placed first or second in every category it entered, and the winner of the optimization category, Mixed-Bag, itself relied on SCIP as a component. After the competition, enabling cut-based conflict analysis and switching the automorphism tool from Nauty to Bliss let the sequential solver solve 782 instances instead of 760, with a 9 percent lower geometric mean runtime. The authors attribute the gains to new separators for RLT cuts and flower inequalities, symmetry detection and handling that covers reflections as well as permutations, and a numerical approach that rounds candidate solutions before feasibility checks.","pith_inferences":["The ablation evidence for RLT cuts and flower inequalities rests on only 3 to 14 affected instances, so the per-feature speedups are not statistically robust and should be re-measured on a larger, unseen benchmark before being taken as general effects.","The paper's success suggests that general MIP solvers may close or reverse the historical gap with SAT-based PB solvers; a direct head-to-head on the same benchmark against solvers like RoundingSat would make this concrete.","The pre-check rounding technique for exact feasibility could be ported to other exact solvers that use floating-point arithmetic, potentially fixing similar artifacts in instances with huge coefficients.","Because the competition benchmark strongly influenced which features were added, the post-competition improvements are at risk of overfitting; a time-locked evaluation on future competition instances would test whether the gains generalize."],"forward_implications":["Pseudo-Boolean problems can be solved at scale by mapping them to integer linear programs and using an LP-based solver, without specialized SAT-style techniques.","Symmetry handling is the single most important feature: disabling it slows affected instances by 35% and loses 13 instances.","RLT cuts and flower inequalities produce large relative speedups on the few instances where they apply (26% and 40% slower when disabled), though these instances are rare.","Cut-based conflict analysis adds a modest but real improvement of 8 instances and 2% average time on instances where it fires.","Parallelizing SCIP with customized racing across 20 cores helps decision problems but not optimization problems, where closing the dual gap matters more."],"supporting_citations":[{"why":"Defines the SCIP constraint integer programming framework that the whole solver and argument build on.","marker":"[2]"},{"why":"Provides the ILP formulation of pseudo-Boolean problems used to apply SCIP to the PB domain.","marker":"[8]"},{"why":"Supplies the efficient separation algorithm for RLT cuts that the paper extends to AND constraints.","marker":"[9]"},{"why":"Introduces the k-flower inequalities that the new flower separator implements.","marker":"[17]"},{"why":"Provides the symmetry detection graphs that let SCIP find permutation and reflection symmetries.","marker":"[30]"},{"why":"Describes the cut-based conflict analysis technique added in the post-competition version.","marker":"[43]"},{"why":"Is the official PB24 competition results page that supplies the performance data.","marker":"[49]"},{"why":"Describes the FiberSCIP shared-memory parallelization that produced the parallel results.","marker":"[52]"}],"fun_headline_variants":["SCIP wins five of six pseudo-Boolean competition classes","Pseudo-Boolean competition: SCIP takes 5 of 6 categories","SCIP solves 782 pseudo-Boolean instances after enhancements","SCIP's pseudo-Boolean method: cuts and symmetry wins","From 759 to 782: SCIP's pseudo-Boolean improvement"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The causal claim that the described features produce the performance gains rests on an ablation study that defines affected instances after seeing the results and runs on the very benchmark that motivated the features, with very few affected instances for two of the features.","fun_headline_variants_meta":{"raw":{"variants":["SCIP wins five of six pseudo-Boolean competition classes","Pseudo-Boolean competition: SCIP takes 5 of 6 categories","SCIP solves 782 pseudo-Boolean instances after enhancements","SCIP's pseudo-Boolean method: cuts and symmetry wins","From 759 to 782: SCIP's pseudo-Boolean improvement"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000903,"raw_usage":{"total_tokens":3828,"prompt_tokens":827,"completion_tokens":3001,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":443,"completion_tokens_details":{"reasoning_tokens":2912}},"tokens_in":443,"tokens_out":3001,"duration_ms":21310,"temperature":1.0,"reasoning_tokens":2912,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:52:40.868627+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run SCIP on a fresh, time-locked set of pseudo-Boolean instances (for example, the next competition's benchmark) with and without each feature individually, using a pre-registered definition of affected instances and a sample large enough for statistical testing; if disabling flower inequalities or RLT cuts no longer slows the solver on affected instances, the paper's attribution fails.","supporting_citations":[{"cited_title":"Constraint Integer Programming","cited_arxiv_id":null,"evidence_quote":"Defines the SCIP constraint integer programming framework that the whole solver and argument build on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the ILP formulation of pseudo-Boolean problems used to apply SCIP to the PB domain."},{"cited_title":"E fficient separation of RLT cuts for implicit and explicit bilinear terms","cited_arxiv_id":null,"evidence_quote":"Supplies the efficient separation algorithm for RLT cuts that the paper extends to AND constraints."},{"cited_title":"Detecting and handling reflection symmetr ies in mixed- integer (nonlinear) programming","cited_arxiv_id":null,"evidence_quote":"Provides the symmetry detection graphs that let SCIP find permutation and reflection symmetries."},{"cited_title":"Pseudo-Boolean competition 2024, 2024","cited_arxiv_id":null,"evidence_quote":"Is the official PB24 competition results page that supplies the performance data."}],"review_version":1}