{"id":"db1180d7-19e9-46a4-9adc-eb71e6f24e19","arxiv_id":"1908.07584","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A worst-bound branching heuristic is proven size-optimal for fixed variable selection and empirically produces much tighter lower bounds for the minimum bandwidth problem than depth-first or breadth-first branching.","lead":"Branching can do more than find solutions: it can prove bounds on the optimal value of a discrete optimization problem. This paper introduces a worst-bound branching heuristic and proves it is size-optimal for fixed variable selection, with strong results on the minimum bandwidth problem.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Condition (c) is the true load-bearing assumption for the optimality claims; any context-dependent relaxation value invalidates Corollaries 2–3, and the paper's general framing overstates the scope.","rationale":"The reader's weakest-assumption analysis correctly identifies condition (c) as the load-bearing hypothesis for Theorem 2 and Corollaries 2–3. My reading of the proof confirms that the cleanup-and-reconstruction argument requires relaxation values to be invariant under changes to the rest of the tree: the thresholds λ_i are defined from node values, and the reverse execution of the worst-bound heuristic must expand exactly the nodes that became open during cleanup. Without (c), adding an unrelated branch could demote or promote an eligible node's value, changing the set of nodes the heuristic must expand and breaking the optimality argument. The paper states (c) explicitly, so the theorem is internally sound under its hypotheses; the concern is scope. The empirical minimum-bandwidth relaxation is a pure function of L and R, so the reported comparisons are likely covered, but the paper's suggestions that constraint propagation and domain filtering can supply relaxation values go beyond the proven regime. For that reason I do not change the reader's conditional verdict: the theoretical result is solid under the stated axioms, while the broader applicability and the reproducibility of the computational study remain conditional on verification. The proposed test directly checks whether the implemented relaxation satisfies (c), which is the one factual question that would determine whether the optimality guarantees cover the reported experiments.","tokens_in":13310,"tokens_out":20658,"duration_ms":656059,"concrete_test":"Reimplement the Section 8 relaxation exactly from Caprara and Salazar-González (2005), Eq. (29) with Props. 12/15, and for a small graph such as the 5-vertex example in Figure 2, compute c(x[u]) for every partial assignment both in isolation and after expanding an unrelated sibling subtree. If any value changes, condition (c) is violated in the implementation and Corollaries 2–3 do not apply to the reported experiments; if no value changes, the theoretical core survives this attack and the conditional verdict stands.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The optimality theorems rest entirely on Section 4 condition (c): the relaxation value at a node is a function solely of the partial assignment x[u], so it cannot change when nodes are added to or removed from the tree. Theorem 2's proof removes leaves by relaxation-value thresholds λ_i to obtain saturated subtrees T_i, then reconstructs them in reverse using the worst-bound heuristic. Each reconstruction step relies on the fact that a node's value is stable while its siblings or descendants change; if relaxing condition (c), the threshold sequence λ_i itself becomes tree-dependent, the intermediate saturated trees are not well-defined, and the reverse execution need not match Algorithm 1. Corollaries 2 and 3 inherit this dependence. The minimum-bandwidth relaxation in Section 8 is defined as an ILP over the fixed sets L and R, so it satisfies (c) when implemented as specified. However, Section 4 also suggests domain filtering and constraint propagation as valid ways to compute relaxation values, and Section 10 extends the method to any problem with a relaxation for fixed variables. Those broader claims do not automatically satisfy (c): propagation, memoized bounds, or learned nogoods from other branches can make a node's relaxation value context-dependent. The central optimality claim is therefore narrower than the paper's general-purpose framing implies.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a 'branching dual' formulation for computing lower bounds in discrete optimization. A partial branching tree is treated as a dual solution, and its value is the bound it proves via relaxation values at open and terminal nodes. The authors define a 'worst-bound heuristic' that expands all open nodes with the current minimum relaxation value, and prove that, when variable selection is fixed, this heuristic is optimal in two senses: it proves any given bound with a minimum-size tree (Corollary 3) and obtains the tightest bound possible from a tree of a given size (Corollary 2). The method is applied to the minimum bandwidth problem by adapting the Caprara–Salazar-González bound to fixed variables, and extensive computational experiments on random, Turner, and Matrix Market instances show that the worst-bound heuristic substantially improves known combinatorial bounds and outperforms depth-first and breadth-first branching with the same relaxation values.","tokens_in":13485,"tokens_out":14583,"duration_ms":140360,"significance":"If the results hold, this is a valuable and fairly general framework for strengthening dual bounds without requiring an integer programming model. The optimality theorems are non-trivial and the computational study is extensive, covering a range of instance sizes and comparing against several baselines. The paper gives explicit proofs of the main claims and provides a concrete relaxation for the minimum bandwidth problem that satisfies the stated assumptions. The absence of code and the garbled typesetting of the relaxation ILP are limitations, but the conceptual contribution and the strength of the empirical improvements are clear.","major_comments":[{"comment":"The optimality results rely critically on condition (c), which states that the relaxation value at a node depends only on the partial assignment x[u]. The paper suggests in §4 that relaxation values 'can also be strengthened by domain filtering and constraint propagation, as in constraint programming,' and §10 extends the method to broader settings. If propagation or other strengthening mechanisms incorporate information from other branches (e.g., memoized bounds or learned nogoods), condition (c) fails and the proofs of Theorem 2 and Corollaries 2–3 break down. The paper should explicitly state that the optimality guarantees are conditional on (c) and should qualify the remarks about propagation and general applicability accordingly.","section":"§4, condition (c); §6, Theorem 2 and Corollaries 2–3"},{"comment":"The proofs of Corollaries 2 and 3 contain an unjustified step: from the fact that T'' is a branching subtree of T' obtained by the worst-bound heuristic and has size at most N, the proof concludes that T'' is a branching subtree of the heuristic's own tree T. This does not follow from fixed variable selection alone. It requires the observation that, with the rule 'expand all eligible nodes simultaneously,' the heuristic's trees form a nested sequence, and any tree produced by the heuristic must be an intermediate tree in that sequence. If the algorithm is terminated mid-iteration at exactly N nodes, the tree T may be a partial expansion of a batch, and the containment claim can fail. The corollaries should be restricted to termination points at the end of a complete expansion round, or the proof should be expanded to show that partial expansions cannot improve the bound and hence the optimal tree of size N must be a complete-round tree.","section":"§6, Corollaries 2 and 3"}],"minor_comments":[{"comment":"There are several typos and inconsistencies: 'a follows' in the Introduction (§1), 'inproves' in §9, and 'WBF-LR' / 'WBF-VS' in Table 1 should be 'WBH-LR' / 'WBH-VS' to match the algorithm name used in the text.","section":"Throughout"},{"comment":"The integer programming relaxation displayed for the minimum bandwidth problem is garbled and difficult to read. Since the formulation is central to the computational results, it should be typeset properly, perhaps with an appendix containing the full derivation, even though the original source (Caprara and Salazar-González 2005) is cited.","section":"§8"},{"comment":"The statement that the worst-bound heuristic is 'polynomial in the number of possible nodes' could be misread as a polynomial-time algorithm; it should clarify that the bound is with respect to the size of the search tree, which may be exponential in the instance size.","section":"§5"},{"comment":"In Algorithm 1, the phrase 'select a label xj(u) for u that does not occur in path P[u]' should be 'that does not already occur in the labels of P[u]' to avoid ambiguity about what is meant by 'occur'.","section":"Algorithm 1"},{"comment":"The paper does not provide code or data for the computational experiments. While not required, providing the instance generator and the relaxation implementation would substantially improve reproducibility.","section":"§9"}],"recommendation":"major_revision","confidential_remarks":"The central theoretical results are likely correct under the stated condition (c), but the paper's presentation overstates the scope of the optimality guarantees and the proof of the two corollaries has a gap that may be fixable. The editor may wish to ask the authors to either restrict the corollaries to complete-round termination or provide a more careful argument for arbitrary N. The empirical claims are strong but would benefit from a clearly typeset relaxation and public code."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Gerry,\n\nThe paper is better than the title's generality suggests, and the proof of the optimality claims is sound under the stated assumptions. The real contribution is the worst-bound heuristic and two optimality theorems for fixed variable selection: it finds the smallest tree for a given bound and the tightest bound for a tree of given size. Those are new, and they are proven from relaxation axioms rather than fitted to data. The min bandwidth study is substantial and shows real improvements over DFS/BFS and over the Caprara–Salazar-González bound. No circularity: the only self-citation is to the earlier branching-dual idea, which doesn't drive the new results.\n\nThe soft spot is condition (c) in Section 4. The relaxation value must depend only on the partial assignment, not on the rest of the tree. The stress-test is right: if you compute relaxation values with propagation, memoized bounds, or learned nogoods from other branches, condition (c) fails and the optimality proofs (Theorem 2 and Corollaries 2–3) collapse. The min-bandwidth relaxation in Section 8 is an ILP over the fixed sets, so it satisfies (c) as implemented. But Section 4 explicitly suggests domain filtering and propagation, and Section 10 extends the method to any problem with a fixed-variable relaxation. That broader framing overstates the scope. The theory is correct for the application shown, but the general message should be qualified.\n\nReproduction is an issue. No code or data are released, the relaxation ILP in Section 8 is garbled, and the conclusion cites Caprara et al. (2011) when the relaxation is from Caprara and Salazar-González (2005). These are fixable, but they matter for a paper whose second half is computational.\n\nWho should read it? People working on lower bounds, branching strategies, and minimum bandwidth heuristics. It deserves a serious referee. I'd send it out, with the expectation of revision: tighten the scope claims around condition (c), release the artifacts, fix the typesetting and citation. The theoretical core is solid enough that a desk reject would be a mistake.","headline":"A sound theory paper with a narrower scope than its title claims; condition (c) is load-bearing and the general applicability framing overstates it, but the worst-bound heuristic and its optimality proofs are a genuine contribution.","tokens_in":14059,"tokens_out":2343,"would_cite":false,"duration_ms":85672,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","90C59"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes a branching dual for discrete optimization and proves that a worst-bound heuristic is optimal for proving bounds when variable selection is fixed.","keywords":["branching dual","dual bounds","worst-bound heuristic","relaxation function","minimum bandwidth","branching tree","fixed variable selection"],"falsifier":"Construct an instance with fixed variable selection where relaxation values are recomputed using global information from other branches (for example, cutting planes or propagation that couples nodes), and find a tree of $N$ nodes that proves a strictly tighter bound than the worst-bound heuristic's tree of $N$ nodes under the same relaxation rule; such a counterexample would show the optimality result depends essentially on the path-only relaxation assumption.","tokens_in":13047,"feed_emoji":"🌳","tokens_out":9405,"duration_ms":89271,"temperature":0.7,"pith_summary":"The paper establishes a general method for obtaining strong lower bounds in discrete optimization by treating partial branching trees as feasible solutions of a dual problem. Its central claim is that a worst-bound heuristic—always expanding the open nodes with the weakest current bound—is optimal for fixed variable selection: it produces the smallest tree that proves a given bound, and the tightest bound obtainable from a tree of a given size. The method works even when no useful integer programming model exists, and the paper illustrates it on the minimum bandwidth problem, where it substantially improves known combinatorial bounds with modest computation. This matters because bound quality determines how quickly exact or heuristic methods can certify proximity to an optimum.","feed_headline":"Worst-bound branching proves tighter bounds with no extra nodes","feed_subtitle":"A dual view of branching trees yields the smallest tree and the tightest bound for a fixed variable order.","key_machinery":"The carrying object is the branching tree as dual solution, equipped with the relaxation function $c(x[u])$: a node's value depends only on the partial assignment along the path from the root, not on the rest of the tree (condition (c)). The dual value of a tree is $\\theta(T)=\\min_{u\\text{ open or terminal}} c_u$, and the worst-bound heuristic (Algorithm 1) repeatedly expands every open node attaining this minimum. Monotonicity of relaxation values with depth makes $\\theta$ nondecreasing as the tree grows, so the heuristic cannot cycle, and condition (c) is exactly what lets the optimality proofs compare trees of different shapes.","core_discovery":"The central discovery is the branching dual of a finite-domain optimization problem: a partial branching tree $T$ proves the lower bound $\\theta(T)=\\min\\{c_u\\mid u\\text{ open or terminal}\\}$, where $c_u=c(x[u])$ is a relaxation value depending only on the partial assignment $x[u]$. Because a complete tree—one in which every nonterminal node is closed or infeasible—leaves no feasible partial assignment unexplored, it proves the exact optimal value, so the dual is strong with no duality gap. The paper proves that for fixed variable selection, the worst-bound heuristic—expand every open node whose relaxation value equals the current $\\theta(T)$—is optimal in both of the senses above (Corollaries 2 and 3). It also gives a more general theorem: given any tree establishing a bound $\\lambda$, the heuristic can be run so as to build a subtree establishing the same $\\lambda$. On the minimum bandwidth problem, the heuristic, with and without greedy variable selection, improves on the Chvátal density bound and the bounds of Blum et al. and Caprara–Salazar-González, often reaching the optimal value within 10,000 internal nodes.","pith_inferences":["The dual-tree construction transfers immediately to mixed-integer programming, where LP relaxation values depend only on the fixed variables, so the same optimality guarantee would hold for branch-and-bound nodes.","The greedy variable-selection variant is effectively learning a branching rule at runtime; one could apply stronger candidate scoring (e.g., approximations of strong branching) within the same worst-bound loop to push bound quality further per node.","Because the heuristic's frontier stays far below breadth-first's, the node-limit optimality result is a practical stand-in for a frontier-size guarantee in memory-constrained settings."],"forward_implications":["For any fixed variable selection, a tree of $N$ nodes grown by the worst-bound heuristic proves the tightest bound that any $N$-node tree can prove, so a computation budget translates directly into a bound-quality guarantee.","For any fixed variable selection, the first tree the heuristic produces that proves a target bound $\\lambda$ is the smallest tree establishing $\\lambda$; bound-proving effort is spent only on branches that matter.","Because the branching dual is strong, the bound converges to the exact optimum as the tree grows, unlike bounds from a partial Lagrangian relaxation that can be stopped short by a duality gap.","On the minimum bandwidth problem, worst-bound branching improves the best known graph-theoretic lower bounds after only 100 internal nodes and frequently closes the gap to optimality within 10,000 nodes, with smaller frontiers than breadth-first search."],"supporting_citations":[{"why":"introduces the density bound for minimum bandwidth, the starting point and baseline that the branching dual strengthens.","marker":"Chvátal (1970)"},{"why":"proposes a polynomial 1/2-approximation of the density bound that serves as one of the graph-theoretic baselines in the experiments.","marker":"Blum et al. (1998)"},{"why":"provides the polynomial bandwidth bound and its fixed-position adaptation used to define relaxation values at tree nodes.","marker":"Caprara and Salazar-González (2005)"},{"why":"supplies the random-instance model with controlled bandwidth used to generate the Turner test sets.","marker":"Turner (1986)"},{"why":"introduces branching duality and the idea of solving it by local search, which the paper formalizes and instantiates.","marker":"Hooker (2012)"},{"why":"proves a best-first node-selection optimality result for fixed variable selection that the paper strengthens and extends to bound-proving.","marker":"Achterberg (2007)"}],"fun_headline_variants":["Branching dual gives tighter bounds for discrete optimization","Worst-bound branching optimal for bounding trees","Dual perspective improves branching bounds","Branching dual proves stronger bounds with tree search","Heuristic branching dual outperforms known bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a node's relaxation value is a function only of the partial assignment on the path to that node, so adding other branches to the tree never changes the bound that a subtree proves; without this, the optimality theorems for the worst-bound heuristic no longer follow.","fun_headline_variants_meta":{"raw":{"variants":["Branching dual gives tighter bounds for discrete optimization","Worst-bound branching optimal for bounding trees","Dual perspective improves branching bounds","Branching dual proves stronger bounds with tree search","Heuristic branching dual outperforms known bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000175,"raw_usage":{"total_tokens":1269,"prompt_tokens":910,"completion_tokens":359,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":526,"completion_tokens_details":{"reasoning_tokens":293}},"tokens_in":526,"tokens_out":359,"duration_ms":4504,"temperature":1.0,"reasoning_tokens":293,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:04:33.084064+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct an instance with fixed variable selection where relaxation values are recomputed using global information from other branches (for example, cutting planes or propagation that couples nodes), and find a tree of $N$ nodes that proves a strictly tighter bound than the worst-bound heuristic's tree of $N$ nodes under the same relaxation rule; such a counterexample would show the optimality result depends essentially on the path-only relaxation assumption.","supporting_citations":[{"cited_title":"Proceedings of the thirtieth annual ACM symposium on Theory of computing, 100--105 (ACM)","cited_arxiv_id":null,"evidence_quote":"proposes a polynomial 1/2-approximation of the density bound that serves as one of the graph-theoretic baselines in the experiments."},{"cited_title":"INFORMS Journal on Computing 17:356--373","cited_arxiv_id":null,"evidence_quote":"provides the polynomial bandwidth bound and its fixed-position adaptation used to define relaxation values at tree nodes."},{"cited_title":"SIAM journal on computing 15(2):561--580","cited_arxiv_id":null,"evidence_quote":"supplies the random-instance model with controlled bandwidth used to generate the Turner test sets."},{"cited_title":"(Springer)","cited_arxiv_id":null,"evidence_quote":"introduces branching duality and the idea of solving it by local search, which the paper formalizes and instantiates."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"proves a best-first node-selection optimality result for fixed variable selection that the paper strengthens and extends to bound-proving."}],"review_version":1}