{"id":"bfa448b5-684d-4859-beaa-97fa37750058","arxiv_id":"1908.07076","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A Lagrangian relaxation on relaxed decision diagrams, with nodes merged only on exact state variables, yields very tight lower bounds and some first optimality proofs for classic single-machine scheduling benchmarks.","lead":"This paper proposes a way to compute tight lower bounds on job scheduling problems by relaxing decision diagrams and solving a Lagrangian dual. The method proves that some best-known benchmark solutions are within a fraction of a percent of optimal, and in several cases exactly optimal.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Biskup-Feldman optimality claims depend on unverified target values from [25]; Table 2's zero-gap rows need independent confirmation.","rationale":"The theoretical framework in Sections 3–6 appears internally coherent: Theorem 2's conditions—exact state variables for costs and penalties—are sufficient, and the all-different dualization via arc penalties is standard. The computational results are therefore the only support for the paper's central claim that DD-based Lagrangian bounds prove near-optimality, and sometimes optimality, for Biskup-Feldman instances. That support is conditional on the Table 2 targets being correct feasible upper bounds. The paper's failure to provide schedules, data, code, or a correct reference for the CPW targets means a reader cannot distinguish a genuine optimality proof from an artifact of mis-transcribed baselines. The 7-versus-8 optimality count is a concrete sign that at least one number in the text or table is wrong, so the table cannot be taken at face value. This does not invalidate the theory or the method, but it makes the empirical claim conditional on verification. The existing CONDITIONAL verdict already captures this state; my read extends the same provenance concern from the CPW targets (the reader's focus) to the Biskup-Feldman targets, where it is more damaging because the BF optimality proofs are the paper's headline contribution.","tokens_in":12876,"tokens_out":18319,"duration_ms":198417,"concrete_test":"Retrieve [25] and the Biskup-Feldman instance data; reconstruct the target values in Table 2 and confirm each is the objective value of a feasible schedule under the stated (h1,h2) penalized due-window objective. Then take the 7 (or 8) zero-gap rows and solve those instances independently with an exact method—for example, a MILP or CP-SAT model of weighted earliness-tardiness with a common due window, or an exact dynamic program—and check whether the optimal value equals the reported lower bound. If any claimed optimal value differs, the optimality claims fail. As a secondary check, resolve the [8] versus [13] citation for the CPW targets.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 8.4's headline result—'optimality is proved for 8 instances'—rests entirely on equality between the DD Lagrangian bound and the 'target' column of Table 2. Those targets are introduced in Section 8.1 as 'best known solution values reported in [25]', but the paper never displays the corresponding schedules, never states how the ten Biskup-Feldman instances were matched to the (h1,h2) due-window objective of [25], and provides no code or instance-level data. A zero gap proves optimality only if the target is a feasible objective value; if a target was mis-transcribed or computed under a different cost convention, the proof collapses. The provenance problem is even more visible for the CPW table: Section 8.1 says 'Optimal solutions are given in [8]', yet [8] is the Biskup-Feldman benchmark paper, not Crauwels et al. [13]. A concrete internal mismatch reinforces the suspicion: the text claims 8 optimality proofs, but Table 2 displays only 7 zero-gap rows. These issues make the computational pillar of the central claim unverifiable as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a general method for computing Lagrangian lower bounds from relaxed decision diagrams (DDs) for job sequencing problems. The central idea is to restrict node mergers so that the state variables on which the immediate cost functions and the dualized penalty functions depend remain exact, thereby allowing the Lagrangian objective to be evaluated exactly on relaxed paths. The authors prove sufficient conditions for this construction (Theorem 2, Corollary 1), discuss which problem classes are amenable to the approach, and report computational experiments on Crauwels-Potts-Wassenhove (CPW) weighted-tardiness instances and Biskup-Feldman (BF) due-window earliness/tardiness instances. The computational sections report very small gaps to best known or optimal values, including zero-gap rows in the BF table that are interpreted as proofs of optimality for some instances.","tokens_in":13140,"tokens_out":13192,"duration_ms":115528,"significance":"If the computational claims are verifiable, this is a useful contribution: it extends DD-based Lagrangian bounding beyond the earlier TSPTW setting of Bergman et al., provides a clean sufficient condition for applicability in terms of exact state variables, and suggests a practical recipe for producing tight bounds on hard sequencing problems. The theoretical derivation (Theorem 2 and Corollary 1) is straightforward and appears correct. The main weakness is that the computational pillar is not independently checkable as written: the citation for the CPW optimal values is wrong, the BF target values and the exact due-window definition are not specified, and the claim of proving optimality for 8 instances is ambiguous. These issues directly affect the paper's headline claims of very tight bounds and first proven optimality for BF instances.","major_comments":[{"comment":"The sentence 'Optimal solutions are given in [8]' is incorrect, because reference [8] is the Biskup-Feldman benchmark paper, not the source of the Crauwels-Potts-Wassenhove (CPW) instance optima. Please correct the citation and explicitly state the origin of the target column in Table 1; without this, the gap percentages in Table 1 cannot be verified.","section":"Section 8.1, Table 1"},{"comment":"The Biskup-Feldman comparison relies on 'best known solution values reported in [25]', but the paper never specifies how the common due window is computed (e.g., whether d(h)=floor(h*sum_j p_j) is used), never lists the target values or the corresponding schedules, and does not provide code or instance data. Because a zero gap is interpreted as a proof of optimality, the target must be a feasible value for exactly the same objective used in the bound computation. Please provide the exact due-date formula, the target values, and a precise data pointer or an appendix with the instance data.","section":"Section 8.1, Table 2"},{"comment":"The claim 'optimality is proved for 8 instances' is ambiguous: Table 2 shows zero gaps in 8 rows, but these correspond to 6 distinct Biskup-Feldman job sets (20-job instances 1, 6, 7 and 50-job instances 1, 2, 3) across the two due-window settings. Please clarify whether 'instances' means base job sets or (job set, due-window) pairs, and state that a zero gap proves optimality only relative to the displayed target values.","section":"Section 8.4"},{"comment":"The Polyak step-size rule uses the best known solution value as the upper bound theta*. This is valid as an upper bound on the Lagrangian dual optimum only if that value is a feasible solution value for the exact problem. The manuscript does not establish this for the Biskup-Feldman targets from [25], and the wrong citation for the CPW targets compounds the problem. Please explicitly state that all target values are feasible for the identical optimization problem used in the bound computation, or adjust the description of the step-size requirement.","section":"Section 8.2"}],"minor_comments":[{"comment":"The heading contains a typo: 'Decicision' should be 'Decision'.","section":"Section 4 heading"},{"comment":"The immediate cost for the common-due-window problem is written with a single due date d_xi, whereas the Biskup-Feldman objective in Section 8.1 uses two due dates d(h1) and d(h2) for earliness and tardiness. Please specify how the two due dates enter the recursion.","section":"Section 7.1"},{"comment":"Row 10 of the 100-job block appears garbled in the text; please check the formatting of the target, bound, and gap columns.","section":"Table 2, 100-job block"},{"comment":"The phrase 'first time that any of these instances have been solved' is a strong claim; since [25] is a heuristic study, please support it with a literature statement or qualify it as 'first proven-optimality certificates'.","section":"Section 8.4"}],"recommendation":"major_revision","confidential_remarks":"The theoretical core (Theorem 2 and Corollary 1) is sound and the computational idea is interesting. The main obstacle is reproducibility of the computational claims: the CPW target citation is wrong, the BF target values and due-date settings are not specified, and the '8 instances' count is ambiguous. These issues are fixable in revision, so I recommend major revision rather than rejection. I would ask the authors to provide the target values or a data appendix at the revision stage, and to correct the citation and instance-count statements."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper has one genuinely useful idea and one load-bearing weakness. The idea: when building a relaxed decision diagram for a DP model, merging states only when they agree on the exact state variables used by the immediate cost and penalty functions preserves the ability to compute a valid Lagrangian bound. That is a clean, general design rule, stated as Theorem 2 and Corollary 1, and it goes beyond the earlier Bergman et al. DD work, which needed an embedded CP model to get useful bounds. The theoretical part is honestly scoped: the paper itself says TSPTW and state-dependent processing times are bad fits for this approach, and that is consistent with the conditions.\n\nThe computational section is where I hesitate. The claim of very tight bounds for Biskup-Feldman instances is attractive, but it rests on comparing the DD lower bound to a \"target\" column of best-known heuristic values from [25]. A zero gap proves optimality only if the target is a genuinely feasible objective value under the same cost convention. That is not verifiable from the paper: no schedules, no instance matching details for the due window objective, no code or data. The stress-test note is right that this is a real provenance problem. On top of that, Section 8.4 says optimality is proved for 8 instances, but Table 2 shows only 7 zero-gap rows. That is a concrete internal inconsistency that a careful referee would catch immediately. The CPW target citation looks mislabeled too: Section 8.1 points to [8] for optimal CPW values, but [8] is the Biskup-Feldman benchmark paper, not a Crauwels et al. solution source.\n\nI would not call any of this fatal to the method. The bounds are genuine lower bounds regardless of the targets; the merging rule is sound. The computational evidence for the Biskup-Feldman claim is just not reproducible as written. The author should supply the missing data or at least state exactly where the target values come from and correct the 7/8 count.\n\nFor a reader, this paper is worth a place in the literature on DD relaxations. The theoretical criterion for when Lagrangian relaxation works with relaxed DDs is useful on its own. I would send it to a serious referee, but expect the report to demand a corrected, reproducible computational section. I would not cite the Biskup-Feldman optimality claims until they are backed up.","headline":"A clean methodological contribution for Lagrangian bounds on relaxed decision diagrams, but the computational section has a count mismatch and target-value provenance problems that need fixing.","tokens_in":13580,"tokens_out":2904,"would_cite":true,"duration_ms":28386,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90B35","90C39","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Relaxed decision diagrams prove best-known schedules are near-optimal","keywords":["decision diagrams","Lagrangian relaxation","job sequencing","lower bounds","dynamic programming","weighted tardiness","earliness-tardiness scheduling","subgradient optimization"],"falsifier":"Check whether the cited target values for the 40- and 50-job weighted-tardiness instances actually appear in the reference given for them. If they do not, recompute the reported gaps by solving those instances with an independent exact method; a true optimum below the reported bound would invalidate the comparison.","tokens_in":12699,"feed_emoji":"⏱️","tokens_out":5895,"duration_ms":55627,"temperature":0.7,"pith_summary":"This paper shows how to compute provable lower bounds for job sequencing problems by solving a Lagrangian dual on a relaxed decision diagram. The key restriction is to merge diagram nodes only when they agree on the state variables that the cost and the dualized constraints depend on; under that condition the bound can be computed by a shortest-path recursion. The method yields very small gaps on benchmark instances: for the common-due-date earliness/tardiness instances it proves for the first time that the best known solutions are within a small fraction of one percent of optimal, and optimal in eight cases. The same conditions identify which dynamic programming models can benefit from this bounding technique.","feed_headline":"Relaxed diagrams prove best-known schedules near-optimal","feed_subtitle":"Merging decision-diagram nodes only on key state variables yields tight lower bounds for hard sequencing problems.","key_machinery":"The central object is the exact state variable in the dynamic programming recursion underlying the decision diagram. A relaxed decision diagram is built by merging nodes only when they agree on the state variables that appear in the immediate cost and in the dualized all-different constraint's penalty function. This restricted merger keeps the recursion valid for Lagrangian relaxation, allowing the bound to be obtained by solving a shortest-path problem in the relaxed diagram; a subgradient method with step sizes based on an upper bound is used to maximize the dual bound.","core_discovery":"The paper's central claim is that Lagrangian relaxation can be implemented in a relaxed decision diagram and yield tight lower bounds, provided the immediate cost function and the immediate penalty function depend only on exact state variables. Formally, Theorem 2 and its corollary say that nodes may be merged only when their states agree on those variables; then the shortest path in the relaxed diagram, with Lagrangian penalties added to arc costs, is a valid lower bound. The paper applies this to single-machine scheduling with state-independent processing times and time windows, and reports gaps mostly below 0.1 percent for the common-due-date earliness/tardiness benchmark, proving optimality for eight instances.","pith_inferences":["The choice of which state variables to keep exact acts as a tunable knob between diagram width and bound tightness; one could automate the selection by measuring how much each state variable affects the cost.","The same bounding scheme could be applied to other combinatorial problems with an all-different constraint, such as vehicle routing or rostering, whenever the cost function can be expressed with a small exact state.","A very small gap between the Lagrangian bound and a heuristic solution can be read as a certificate that the heuristic is near-optimal; this is the practical use the paper motivates but does not itself implement as a decision rule."],"forward_implications":["For weighted-tardiness scheduling with state-independent processing times, relaxed-DD Lagrangian bounds are below 1 percent for most tested instances and below 0.1 percent for about a quarter of them.","For the common-due-date earliness/tardiness benchmark, the best known solutions are within a small fraction of one percent of optimality, and eight instances are proven optimal.","Problems whose immediate cost depends on state variables that cannot be kept exact, such as the traveling salesman problem with time windows or state-dependent processing times, are unlikely to benefit from a stand-alone relaxed-DD Lagrangian bound.","The same exact-state criteria apply to deterministic dynamic programming models in general, so the technique extends beyond scheduling when the conditions hold."],"supporting_citations":[{"why":"Introduces the combination of Lagrangian relaxation with decision diagrams, the starting point this paper extends to stand-alone relaxed diagrams.","marker":"[3]"},{"why":"Supplies the relaxation conditions for node merging and the earlier observation that Lagrangian relaxation could strengthen bounds from smaller diagrams.","marker":"[20]"},{"why":"Provides the common-due-date benchmark instances used in the main computational comparison.","marker":"[8]"},{"why":"Provides the weighted-tardiness benchmark instances whose optimal and best-known values are used as targets.","marker":"[13]"},{"why":"Supplies the best-known solution values for the common-due-date instances, the heuristic results the new bounds are compared against.","marker":"[25]"},{"why":"Provides the subgradient step-size rule used to solve the Lagrangian dual.","marker":"[23]"}],"fun_headline_variants":["Lagrangian relaxation on relaxed decision diagrams tightens sequencing bounds","Decision diagram relaxations yield near-optimal lower bounds for scheduling","Tighter bounds for job sequencing via Lagrangian decision diagrams","Biskup-Feldman schedules proven within 1% of optimal","New proof: relaxed decision diagrams give tight sequencing bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The computational comparison depends on the assumption that the target values cited for the weighted-tardiness benchmark instances are the true optimal (or best known) values; the text attributes these targets to a reference that is actually the common-due-date benchmark paper, so the provenance of those numbers is not verified.","fun_headline_variants_meta":{"raw":{"variants":["Lagrangian relaxation on relaxed decision diagrams tightens sequencing bounds","Decision diagram relaxations yield near-optimal lower bounds for scheduling","Tighter bounds for job sequencing via Lagrangian decision diagrams","Biskup-Feldman schedules proven within 1% of optimal","New proof: relaxed decision diagrams give tight sequencing bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000887,"raw_usage":{"total_tokens":3743,"prompt_tokens":776,"completion_tokens":2967,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":392,"completion_tokens_details":{"reasoning_tokens":2894}},"tokens_in":392,"tokens_out":2967,"duration_ms":21713,"temperature":1.0,"reasoning_tokens":2894,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:27:36.714866+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Check whether the cited target values for the 40- and 50-job weighted-tardiness instances actually appear in the reference given for them. If they do not, recompute the reported gaps by solving those instances with an independent exact method; a true optimum below the reported bound would invalidate the comparison.","supporting_citations":[{"cited_title":"Constraints 20, 346–361 (2015)","cited_arxiv_id":null,"evidence_quote":"Introduces the combination of Lagrangian relaxation with decision diagrams, the starting point this paper extends to stand-alone relaxed diagrams."},{"cited_title":"In: Beck, J.C","cited_arxiv_id":null,"evidence_quote":"Supplies the relaxation conditions for node merging and the earlier observation that Lagrangian relaxation could strengthen bounds from smaller diagrams."},{"cited_title":"Computers and Operations Research 28, 787–801 (2001)","cited_arxiv_id":null,"evidence_quote":"Provides the common-due-date benchmark instances used in the main computational comparison."},{"cited_title":"INFORMS Journal on Computing 10, 341–350 (1998)","cited_arxiv_id":null,"evidence_quote":"Provides the weighted-tardiness benchmark instances whose optimal and best-known values are used as targets."},{"cited_title":"International Journal of Production Research 55, 1707–1719 (2017)","cited_arxiv_id":null,"evidence_quote":"Supplies the best-known solution values for the common-due-date instances, the heuristic results the new bounds are compared against."},{"cited_title":"Optimiza- tion Software, New York (1987)","cited_arxiv_id":null,"evidence_quote":"Provides the subgradient step-size rule used to solve the Lagrangian dual."}],"review_version":1}