{"id":"b9b5453f-2eff-4794-b5dd-fa3a2c443a75","arxiv_id":"2412.14382","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Balans uses online multi-armed bandits to adaptively choose among large-neighborhood search operators on top of a MIP solver, reporting large primal gap improvements over default SCIP and Gurobi on hard instances without offline training.","lead":"Balans wraps a mixed-integer programming solver and uses multi-armed bandits to choose, on the fly, which of several large-neighborhood search operators to apply. The paper reports large primal gap reductions over default SCIP and Gurobi on hard benchmark instances, without any offline training.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Missing random/round-robin arm-selection baseline leaves the central attribution to online bandit learning unsupported; portfolio diversity alone could explain the gains.","rationale":"The reader's weakest assumption is precisely the load-bearing gap I see: the paper never isolates the contribution of bandit adaptation from the contribution of having a diverse 16-arm portfolio. The experiments in Section 4.1 establish that some Balans configuration beats SCIP and the tested single neighborhoods on aggregate PG/PI, but they do not establish that the MAB selection mechanism is the reason. A random or round-robin arm selector would be the natural control; its absence is not a minor omission because the paper explicitly argues in Q2 and Table 2 that Balans works by learning to sequence weaker operators. That argument is causal, and arm-selection frequencies alone cannot support it. I also flagged the unsupported use of 'significantly' without paired tests, but that is secondary. My recommendation is to keep the reader's CONDITIONAL verdict: the practical contribution is plausible and well engineered, but the scientific attribution to online learning should be accepted only after the missing control and significance testing are supplied. This is not an objection to the overall value of the system; it is an objection to the strength of the stated claim.","tokens_in":15572,"tokens_out":5094,"duration_ms":48152,"concrete_test":"Run Balans in three selector modes on the same 93 instances (D-MIPLIB 50 + H-MIPLIB 43): (i) MAB best config per dataset, (ii) uniform random arm choice each iteration, (iii) round-robin over the 16 arms, with rewards ignored but otherwise identical time limits, initial solution phase, acceptance criterion, and 1-hour cutoff. Report per-instance paired PG and PI and run a Wilcoxon signed-rank test (or paired t-test) comparing MAB versus each non-adaptive selector. If MAB is not significantly better than random or round-robin on both metrics, the paper's central claim of online-learning-driven gains is unsupported. Also record the random selector's arm frequencies to check whether it also spends most time on the same weaker operators.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The strongest claim in Section 6 is that Balans, without offline training and almost zero tuning, significantly improves over default BnB and every single LNS, and the paper's scientific contribution is that MAB-based online learning is what makes this possible. That contribution is underdetermined by the experiments. Section 4 compares the 16-arm MAB portfolio against single neighborhoods and lb-relax, but never against any non-adaptive selector over the same 16 arms, such as uniform random or round-robin. If a random/round-robin scheduler over the identical portfolio, with identical per-iteration time limits (1 min, 2.5 min for Local Branching) and acceptance criteria, achieves comparable PG/PI, then the improvement over SCIP and over single neighborhoods is explained by the diversity of the arm portfolio and the parameter variations (lb 10/25/50, mutation 25/50/75, etc.), not by bandit adaptation. Table 2's arm-selection frequencies are descriptive and cannot establish that 'exploring and sequencing weaker neighborhoods' causes the gains. In addition, 'significantly' is asserted without paired significance tests; the reported standard deviations overlap across instances, so even the superiority claim itself is not statistically secured. The central scientific claim therefore remains conditional: the practical wrapper may well help, but the mechanism claimed online adaptive learning is not yet tested.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Balans, a meta-solver for mixed-integer programs that wraps a MIP solver (SCIP or Gurobi) in an adaptive large-neighborhood search (ALNS) loop. A portfolio of 16 destroy operators, derived from eight classic neighborhoods with parameter variations, is maintained, and a multi-armed bandit policy selects the next neighborhood online, with rewards based on the acceptance outcome of each repair step. The method requires no offline training. Experiments on D-MIPLIB (50 instances) and a filtered H-MIPLIB subset (43 instances) compare Balans against default SCIP/Gurobi, single-neighborhood LNS, and the lb-relax baseline, reporting primal gap and primal integral at a one-hour limit. The authors claim that all configurations of Balans significantly improve over the default solver and every single-neighborhood approach, and that the bandit-based online adaptation is the key to the gains.","tokens_in":15841,"tokens_out":5886,"duration_ms":48791,"significance":"If the empirical claims are substantiated, Balans is a practically valuable, solver-agnostic, training-free wrapper that improves primal bounds on hard MIPs; the open-source release and the ablation on Gurobi and on SCIP's internal ALNS are useful contributions. The paper's most interesting scientific claim—that online bandit learning sequences weak operators into an effective search—is currently underdetermined by the experiments. The missing non-adaptive control and the lack of statistical testing prevent the paper from establishing the learning attribution, although the practical wrapper may well be beneficial.","major_comments":[{"comment":"The central attribution of the performance gains to online bandit learning is not tested. The paper compares the 16-arm MAB portfolio against single neighborhoods and lb-relax, but never against a non-adaptive selection rule over the same 16 arms, such as uniform random, round-robin, or a fixed cyclic schedule, using identical per-iteration time limits and acceptance criteria. If a random or round-robin scheduler achieves comparable primal gaps and primal integrals, then the improvement over SCIP and over single neighborhoods is explained by the diversity of the portfolio and the parameter variations (lb 10/25/50, mutation 25/50/75, etc.) rather than by adaptive selection. The sentence in §4.1 that Balans improves 'by using weaker operators sequentially and carefully balancing the exploitation-exploration trade-off via online learning' is a causal interpretation that the experiments do not support. A control experiment with a non-adaptive selector is required to support the paper's main claim.","section":"§4.1, Table 1 and Figure 2"},{"comment":"The word 'significantly' is used in the abstract, §1, and §6, but no statistical significance tests are reported. The standard deviations in Table 1 are large relative to the mean differences (for example, D-MIPLIB primal gap for Softmax linear SA is 0.49±0.81 vs SCIP 2.11±1.68), and no per-instance paired comparisons are shown. The '75+%' reduction claim is also presented without a confidence interval. The authors should report paired tests (e.g., Wilcoxon signed-rank) or confidence intervals for the primal gap and primal integral differences to substantiate the 'significant' language.","section":"§4.1, Table 1 and §6"},{"comment":"The comparison against lb-relax is potentially unfair. The paper states in §3.1 that lb-relax 'has a hyper-parameter to control the destroy size that must be chosen carefully for each problem domain,' but §4 does not report the hyper-parameter settings used for lb-relax or whether they were tuned on the test domains. Since the claimed improvement over the state-of-the-art LNS(MIP) relies on this baseline, the authors need to either tune lb-relax per domain, use the authors' recommended settings, or justify that the chosen settings are appropriate. Without this, the aggregate result that lb-relax performs worse than SCIP may be an artifact of an under-tuned baseline.","section":"§4, 'State-of-the-art LNS(MIP)' baseline; §3.1"}],"minor_comments":[{"comment":"The H-MIPLIB subset is filtered to instances that permit a feasible solution within 20 seconds, yielding 43 instances. The paper should discuss how this selection affects the generality of the claim about 'hard optimization problems,' since instances where an initial feasible solution is difficult to find are excluded by construction.","section":"§4, Datasets"},{"comment":"The phrase 'any configuration of BALANS' should be qualified: Table 1 reports 6 learning policies under 2 acceptance criteria (12 configurations), not all possible reward-vector and temperature-schedule choices. The sentence 'any B ALANS configuration is better than the alternatives' should read 'any tested configuration.'","section":"§4.1, Table 1"},{"comment":"The arm-selection distribution is reported only for the 'best BALANS configurations,' but the criterion for 'best' is not defined. Please specify whether this is the configuration with the lowest mean primal gap or primal integral, and report the corresponding distributions for a few other configurations to show stability.","section":"§4.1, Table 2"},{"comment":"The destroy-size variations (e.g., lb 10/25/50) are hand-chosen hyper-parameters, and the time limits (20-second initialization, 1-minute and 2.5-minute iterations) are also configured. The claim of 'almost zero tuning' should be qualified to acknowledge these choices, even if they are not instance-specific.","section":"§3.1 and §4"},{"comment":"The GitHub URL appears as 'https://github.com/anonymous/balans/' in Appendix A but as 'https://github.com/skadio/balans' in the main text; please make these consistent.","section":"Appendix A"},{"comment":"The phrase 'apriori training' should be 'a priori training'; also, the typesetting of 'B ALANS' is inconsistent in places and should be normalized.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The paper is clearly written and the software release is commendable, but the missing random/round-robin control is a standard experimental requirement for any claim that an adaptive policy outperforms a static one. The statistical language also needs tightening. These are fixable within the scope of a revision, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Balans is a well-engineered, training-free ALNS(MIP) wrapper that plausibly improves primal bounds over default SCIP and Gurobi, and over single-neighborhood LNS, on the tested hard instances. The code is released, the ablation with Gurobi is a nice touch, and the comparison against lb-relax is fair. The paper is worth a serious referee.\n\nWhat's actually new: framing ALNS over a MIP solver as a multi-armed bandit problem with 16 parameterized destroy arms, and showing this can beat the default solver and the state-of-the-art single-neighborhood LNS on a mix of instance distributions without offline training. The open-source PyPI release is real evidence and will be useful as a baseline.\n\nThe soft spot is the attribution. The central claim is that online bandit selection is what drives the gains, but the experiments never compare against a uniform random or round-robin selector over the same 16 arms under the same time limits and acceptance criteria. If a random scheduler does just as well, the improvement is explained by portfolio diversity and parameter variation, not by adaptation. The arm-selection frequencies in Table 2 are descriptive and don't prove causation. Also, 'significantly' is used without paired significance tests, and the standard deviations in Table 1 are large enough that the difference between Balans and SCIP on some instances may not be statistically secured.\n\nNone of this kills the practical contribution. The improvements over default solvers are large in aggregate and consistent across most configurations and both solvers. But the paper should add the random/round-robin baseline and significance testing before claiming bandit adaptation as the mechanism. That's a load-bearing omission for the scientific story, not a cosmetic one.\n\nThe paper is for practitioners in combinatorial optimization who want a cheap way to improve primal bounds, and for ML4CO researchers who need an online-learning baseline. I'd cite it if I'm benchmarking LNS(MIP) wrappers.\n\nRecommendation: send to peer review. The missing baseline and significance tests are addressable in revision. The engineering and the empirical scope justify referee time.","headline":"Balans is a well-engineered ALNS(MIP) wrapper that plausibly improves primal bounds in practice, but the paper's central claim that bandit adaptation drives the gains is untested because there is no random/round-robin baseline.","tokens_in":16359,"tokens_out":2066,"would_cite":true,"duration_ms":15632,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Balans claims that steering large-neighborhood search with multi-armed bandits, with no offline training, beats both the default solver and every single-neighborhood search on hard MIPs.","keywords":["mixed-integer programming","adaptive large neighborhood search","multi-armed bandits","online learning","primal heuristics","neighborhood selection","MIP meta-solver","branch-and-bound"],"falsifier":"Run the same 16-arm portfolio with random or round-robin selection, using identical destroy sizes, acceptance criteria, time limits, and instance sets; if it matches Balans's primal gap and primal integral, the central claim that adaptive bandit learning drives the improvement is falsified.","tokens_in":15396,"feed_emoji":"🎰","tokens_out":11826,"duration_ms":90371,"temperature":0.7,"pith_summary":"Balans is a meta-solver for mixed-integer programming (MIP) that wraps an existing MIP solver inside an adaptive large-neighborhood search loop, using multi-armed bandits to choose on the fly which destroy-and-repair neighborhood to apply next. The paper's central claim is that every tested configuration of this online approach, with no offline training and almost no tuning, significantly improves over the default branch-and-bound solver and over any single-neighborhood large-neighborhood search, including the previous state-of-the-art local-branching relaxation, on hard MIP instances. This matters because learning-based MIP heuristics typically need expensive offline training and generalize poorly, whereas Balans learns from its own search trajectory and works on top of both SCIP and Gurobi. The paper reports reducing SCIP's primal gap by more than 75 percent and its primal integral by more than 50 percent on two hard benchmark sets, with the weak standalone operators RENS and RINS dominating the bandit's arm selections.","feed_headline":"Bandit search with no training cuts MIP primal gap by 75%","feed_subtitle":"Adaptively swapping destroy neighborhoods beats default solvers and every single-neighborhood search on hard instances.","key_machinery":"The central object is the bandit-steered adaptive large-neighborhood search loop, ALNS(MIP), layered over a MIP solver. A portfolio of 16 arms is built from six unique destroy operators, Crossover, Local Branching, Mutation, Proximity, RENS, and RINS, each repeated at several destroy-size settings; selecting an arm destroys part of the current solution and immediately repairs it by re-optimizing the resulting sub-MIP. The reward signal is categorical, best, better, accepted, or rejected under the state-acceptance criterion, mapped to numeric or binary rewards, and e-Greedy, Softmax, and Thompson Sampling policies update arm estimates after each pull. The loop keeps a single MIP model and its root LP relaxation incrementally across iterations, which is what makes repeated destroy-repair calls computationally feasible.","core_discovery":"The discovery, stated on the paper's own terms, is that treating a portfolio of large-neighborhood-search operators as arms in a multi-armed bandit converts individually weak destroy operators into a search that beats both the default MIP solver and any single-neighborhood search. The bandit rewards each arm according to four acceptance-criterion outcomes (best, better, accepted, rejected) and continuously updates its choice policy, using e-Greedy, Softmax, or Thompson Sampling, as the solve progresses. Arm-selection statistics show that the single best standalone operator, local branching, is chosen only 0.6 percent of the time on H-MIPLIB, while RENS and RINS, which are poor when run alone, together account for roughly 40 percent of selections on D-MIPLIB and 60 percent on H-MIPLIB; the paper concludes that the gain comes from sequencing weaker neighborhoods with a deliberate exploration-exploitation balance. The claim is asserted for hard benchmark instances from D-MIPLIB and a feasible subset of MIPLIB2017-Hard, within a one-hour time limit, under both Hill Climbing and Simulated Annealing acceptance criteria, and the authors state that all configurations, without offline training and almost zero tuning, improve over the baselines.","pith_inferences":["Beyond the paper's reported experiments, a random or round-robin control over the same 16 arms would separate the contribution of bandit learning from the contribution of portfolio diversity; the paper does not include this control.","If learning is the cause, the heavy selection of RENS and RINS suggests a smaller portfolio with only a few weak operators and randomized destroy sizes might reproduce much of the gain at lower per-iteration cost.","A natural extension is to add offline-learned LNS policies as additional arms, a hybrid the authors list as future work; this would let training-based and training-free guidance compete and cooperate in one search.","Logging per-iteration regret or switching costs would show whether the advantage comes from early adaptation or steady-state scheduling, which the aggregate traces do not distinguish."],"forward_implications":["On any hard instance, running Balans with default settings should produce better primal bounds within one hour than the stock SCIP or Gurobi solver, because every tested bandit configuration beat both baselines on D-MIPLIB and H-MIPLIB.","A practitioner no longer needs to pick a neighborhood and tune its destroy size: parameter variations are exposed as arms and selected online, avoiding the per-domain tuning that single-neighborhood LNS requires.","The solver-agnostic design means the same wrapper can be placed on top of open-source or commercial MIP solvers, and the experiments show the improvement pattern holds for SCIP and Gurobi.","The internal adaptive large-neighborhood search already inside SCIP explains little of the gain: the ablation attributes improvement on 79 of 94 instances to the bandit-based outer loop, with SCIP's internal ALNS helping only 8 instances by less than 0.2 percent gap.","Weak operators can be load-bearing: RENS and RINS, poor standalone, account for roughly 40 to 60 percent of arm selections in the best configurations, so a diverse, adaptively scheduled portfolio outperforms committing to the single best neighborhood."],"supporting_citations":[{"why":"Supplies the state-of-the-art local-branching relaxation (lb-relax) baseline that Balans must outperform.","marker":"Huang et al., 2023a"},{"why":"SCIP is the default branch-and-bound baseline and the working MIP solver inside Balans for the main experiments.","marker":"Bolusani et al., 2024"},{"why":"Gurobi is the second MIP solver used in the ablation that supports the solver-agnostic claim.","marker":"Gurobi, 2024"},{"why":"D-MIPLIB provides the multi-domain hard benchmark instances drawn from five problem families.","marker":"Huang et al., 2024"},{"why":"MIPLIB2017-Hard provides the second benchmark set of hard instances that cannot be solved to optimality within an hour.","marker":"Gleixner et al., 2021"},{"why":"Establishes the LNS-on-top-of-a-MIP-solver paradigm that Balans extends to adaptive multi-neighborhood search.","marker":"Song et al., 2020"},{"why":"Defines the Crossover and Mutation destroy operators used as arms in the Balans portfolio.","marker":"Rothberg, 2007"},{"why":"Defines Local Branching, the single best neighborhood whose parameter variants become arms.","marker":"Fischetti and Lodi, 2003"},{"why":"Defines RENS, a weak standalone operator that is heavily selected by the bandit in the reported traces.","marker":"Berthold, 2014"},{"why":"Defines RINS, the other weak standalone operator that dominates arm selection in the traces.","marker":"Danna et al., 2005"}],"fun_headline_variants":["Bandit-chosen destroy operators beat default MIP solver, no training","No-training bandit search for MIP: 75% better primal gaps","Adaptive LNS with multi-armed bandits: offline training obsolete","Balans: bandit meta-solver for MIPs, learns on the fly","MIP solving gets online learning: bandit-guided neighborhoods win"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the gains come from learning to choose neighborhoods online, not just from having 16 diverse neighborhoods to try; if random or round-robin selection over the same arms matched Balans's results, the learning claim would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Bandit-chosen destroy operators beat default MIP solver, no training","No-training bandit search for MIP: 75% better primal gaps","Adaptive LNS with multi-armed bandits: offline training obsolete","Balans: bandit meta-solver for MIPs, learns on the fly","MIP solving gets online learning: bandit-guided neighborhoods win"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000706,"raw_usage":{"total_tokens":3223,"prompt_tokens":1030,"completion_tokens":2193,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":646,"completion_tokens_details":{"reasoning_tokens":2095}},"tokens_in":646,"tokens_out":2193,"duration_ms":14477,"temperature":1.0,"reasoning_tokens":2095,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:16:33.315864+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same 16-arm portfolio with random or round-robin selection, using identical destroy sizes, acceptance criteria, time limits, and instance sets; if it matches Balans's primal gap and primal integral, the central claim that adaptive bandit learning drives the improvement is falsified.","supporting_citations":[{"cited_title":"Gurobi Optimizer Reference Manual , 2024","cited_arxiv_id":null,"evidence_quote":"Gurobi is the second MIP solver used in the ablation that supports the solver-agnostic claim."},{"cited_title":"Learning to schedule heuristics in branch and bound","cited_arxiv_id":null,"evidence_quote":"MIPLIB2017-Hard provides the second benchmark set of hard instances that cannot be solved to optimality within an hour."},{"cited_title":"An evolutionary algorithm for polishing mixed integer programming solutions","cited_arxiv_id":null,"evidence_quote":"Defines the Crossover and Mutation destroy operators used as arms in the Balans portfolio."},{"cited_title":"Local branching","cited_arxiv_id":null,"evidence_quote":"Defines Local Branching, the single best neighborhood whose parameter variants become arms."},{"cited_title":"Rens: the optimal rounding","cited_arxiv_id":null,"evidence_quote":"Defines RENS, a weak standalone operator that is heavily selected by the bandit in the reported traces."},{"cited_title":"Exploring relaxation induced neighborhoods to improve mip solutions","cited_arxiv_id":null,"evidence_quote":"Defines RINS, the other weak standalone operator that dominates arm selection in the traces."}],"review_version":1}