Improved Job sequencing Bounds from Decision Diagrams

J. N. Hooker

REVIEW 4 major objections 4 minor 25 references

Improved Job sequencing Bounds from Decision Diagrams

T0 review · 4 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Relaxed decision diagrams prove best-known schedules are near-optimal

desk verdict 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. read the letter →

arxiv 1908.07076 v1 pith:YVXOHHYG submitted 2019-08-19 cs.DS

J. N. Hooker This is my paper · ORCID

classification cs.DS MSC 90B3590C3990C27

keywords decisiondiagramsLagrangianrelaxationjobsequencinglowerboundsdynamicprogrammingweightedtardinessearliness-tardinessschedulingsubgradientoptimization

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

I 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.

For 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.

Referee Report

4 major / 4 minor

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.

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 (4)

[Section 8.1, Table 1] 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 8.1, Table 2] 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 8.4] 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 8.2] 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.

minor comments (4)

[Section 4 heading] The heading contains a typo: 'Decicision' should be 'Decision'.
[Section 7.1] 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.
[Table 2, 100-job block] Row 10 of the 100-job block appears garbled in the text; please check the formatting of the target, bound, and gap columns.
[Section 8.4] 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'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower bounds are genuine computed bounds, not fitted values, and the derivation from relaxed decision diagrams to Lagrangian bounds is self-contained.

full rationale

The central derivation is not circular. The relaxed DD bound is obtained by solving a shortest-path problem in a relaxed decision diagram, and the Lagrangian dual is a standard valid lower-bounding mechanism (θ(λ) is a lower bound for any λ). Theorem 2 and Corollary 1 provide sufficient conditions for implementing the Lagrangian relaxation in the relaxed DD; these are proven in the paper, not assumed by construction. The use of the best-known solution value as an upper bound in Polyak's step-size rule affects only convergence, not the validity of the computed lower bound, and the bound is not fitted to the target. The comparisons with CPW and Biskup-Feldman targets are external benchmark comparisons, not reductions of the claimed results to the inputs. The reliance on Theorem 1 from the author's prior work [20] is a legitimate citation of a stated, parameter-free sufficient condition for valid node mergers, and it does not import the paper's own conclusions. The apparent reference mismatch in Section 8.1, where optimal CPW values are attributed to [8] (the Biskup-Feldman paper), and the discrepancy between the textual claim of 8 optimality proofs and the 7 displayed zero-gap rows, are correctness and reproducibility concerns, not circularity. No step in the derivation is equivalent by definition to its own output, and no fitted parameter is renamed as a prediction. Therefore the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The central model has no fitted free parameters; it relies on prior results from [20], standard scheduling DP formulations, and empirical convergence assumptions. The main latent assumption is that the relaxed DDs remain small for the selected problem classes, which is validated only experimentally.

assumptions (7)

domain assumption Theorem 1 of [20]: merging nodes with states Si and Ti under a relaxation operator yields a valid relaxation when Si⊕Ti relaxes both Si and Ti, and relaxation is preserved by the transition function.
Quoted in Section 5 and used without proof; it is prior work by the same author and is not machine-checked in this paper.
standard math Lemma 1: a state variable is exact when states are merged only if their values on that variable agree.
Stated as easy to show in Section 5; used to ensure immediate cost and penalty functions are computable on relaxed DD paths.
domain assumption The relaxation operator for job sequencing states, (Vi∩Vi', min{ti,ti'}), is a valid relaxation for the tardiness DP.
Adopted from [20] and used throughout Sections 6 and 7; validity is not re-proved here.
domain assumption The DP recursion (1) with state (Vi,ti) and immediate cost (2) correctly models minimum total tardiness.
Standard DP formulation for single-machine scheduling with release dates and due dates, used without derivation.
domain assumption For Biskup-Feldman earliness/tardiness models, the state variables si and ti remain equal under the merge rule, so a single exact finish-time variable suffices.
Used in Section 7.1 to justify practicality; follows from the transition functions adding the same processing time to both variables.
domain assumption The Biskup-Feldman instances are defined with common due dates d(h)=floor(h * sum_j p_j), and the comparison targets from [25] are feasible schedules.
Section 8.1; the equality of bound and target is interpreted as a proof of optimality only if targets are feasible.
ad hoc to paper Polyak subgradient optimization with the stated step size and 50,000 iterations yields near-optimal Lagrangian dual bounds on the test instances.
Empirical claim in Sections 8.2-8.4; no convergence certificate is provided, so the reported tightness is not guaranteed.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Improved Job sequencing Bounds from Decision Diagrams." pith.science (2026). https://pith.science/paper/YVXOHHYG

@misc{pith2026190807076,
  author       = {Pith},
  title        = {Pith review of: Improved Job sequencing Bounds from Decision Diagrams},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YVXOHHYG}},
  note         = {Machine review of arXiv:1908.07076}
}

read the original abstract

We introduce a general method for relaxing decision diagrams that allows one to bound job sequencing problems by solving a Lagrangian dual problem on a relaxed diagram. We also provide guidelines for identifying problems for which this approach can result in useful bounds. These same guidelines can be applied to bounding deterministic dynamic programming problems in general, since decision diagrams rely on DP formulations. Computational tests show that \mbox{Lagrangian} relaxation on a decision diagram can yield very tight bounds for certain classes of hard job sequencing problems. For example, it proves for the first time that the best known solutions for Biskup-Feldman instances are within a small fraction of 1% of the optimal value, and sometimes optimal.

Figures

Figures reproduced from arXiv: 1908.07076 by the authors.

**Figure 2.** A relaxation of the decision diagram in [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

[25]

International Journal of Production Research 55, 1707–1719 (2017)

Ying, K.C., Lin, S.W., Lu, C.C.: Eﬀective dynamic dispatching rule and constructive heuristic for solving single-machine scheduling problems with a common due window. International Journal of Production Research 55, 1707–1719 (2017)

work page 2017
[8]

Computers and Operations Research 28, 787–801 (2001)

Biskup, D., Feldman, M.: Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates. Computers and Operations Research 28, 787–801 (2001)

work page 2001
[1]

In: Bessi` ere, C

Andersen, H.R., Hadˇ zi´ c, T., Hooker, J.N., Tiedemann, P.: A constraint store based on multivalued decision diagrams. In: Bessi` ere, C. (ed.) Principles and Practice of Constraint Programming (CP 2007). LNCS, vol. 4741, pp. 118–132. Springer (2007)

work page 2007
[2]

In: Pesant, G

Bergman, D., Cir´ e, A.A., van Hoeve, W.J.: Improved constraint propagation via Lagrangian decomposition. In: Pesant, G. (ed.) Principles and Practice of Constraint Programming (CP 2015). LNCS, vol. 9255, pp. 30–38. Springer (2015)

work page 2015
[3]

Constraints 20, 346–361 (2015)

Bergman, D., Cir´ e, A.A., van Hoeve, W.J.: Lagrangian bounds from decision diagrams. Constraints 20, 346–361 (2015)

work page 2015
[4]

INFORMS Journal on Computing 26, 253–268 (2013)

Bergman, D., Cir´ e, A.A., van Hoeve, W.J., Hooker, J.N.: Optimization bounds from binary decision diagrams. INFORMS Journal on Computing 26, 253–268 (2013)

work page 2013
[5]

INFORMS Journal on Computing 28, 47–66 (2014)

Bergman, D., Cir´ e, A.A., van Hoeve, W.J., Hooker, J.N.: Discrete optimization with binary decision diagrams. INFORMS Journal on Computing 28, 47–66 (2014)

work page 2014
[6]

Springer (2016)

Bergman, D., Cir´ e, A.A., van Hoeve, W.J., Hooker, J.N.: Decision Diagrams for Optimization. Springer (2016)

work page 2016

Show all 25 references

[7]

In: Proceedings of CPAIOR

Bergman, D., van Hoeve, W.J., Hooker, J.N.: Manipulating MDD relaxations for combinatorial optimization. In: Proceedings of CPAIOR. LNCS, vol. 6697, pp. 20–35 (2011)

2011
[9]

European Journal of Operational Research 162, 740–761 (2005)

Biskup, D., Feldman, M.: On scheduling around large restrictive common due windows. European Journal of Operational Research 162, 740–761 (2005)

2005
[10]

IEEE Transactions on Computers C-35, 677–691 (1986)

Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers C-35, 677–691 (1986)

1986
[11]

European Journal of Operational Research 93, 49–60 (1996)

Chen, Z.L.: Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs. European Journal of Operational Research 93, 49–60 (1996)

1996
[12]

Operations Research 61, 1411–1428 (2013)

Cir´ e, A.A., van Hoeve, W.J.: Multivalued decision diagrams for sequencing problems. Operations Research 61, 1411–1428 (2013)

2013
[13]

INFORMS Journal on Computing 10, 341–350 (1998)

Crauwels, H., Potts, C., Wassenhove, L.V.: Local search heuristics for the single machine total weighted tardiness scheduling problem. INFORMS Journal on Computing 10, 341–350 (1998)

1998
[14]

Operations Research 43, 367– 371 (1995)

Dumas, Y., Desrosiers, J., Gelinas, E., Solomon, M.M.: An optimal algorithm for the traveling salesman problem with time windows. Operations Research 43, 367– 371 (1995)

1995
[15]

In: Loute, E., Wolsey, L

Hadˇ zi´ c, T., Hooker, J.N.: Cost-bounded binary decision diagrams for 0-1 programming. In: Loute, E., Wolsey, L. (eds.) CPAIOR 2007 Proceedings. LNCS, vol. 4510, pp. 84–98. Springer (2007)

2007
[16]

Operations Research 39, 836–846 (1991)

Hall, N.G., Posner, M.E.: Earliness-tardiness scheduling problems, I: Weighted deviation of completion times about a common due date. Operations Research 39, 836–846 (1991)

1991
[17]

Operations Research 39, 847–856 (1991)

Hall, N.G., Posner, M.E., Sethi, S.P.: Earliness-tardiness scheduling problems, II: Weighted deviation of completion times about a restrictive common due date. Operations Research 39, 847–856 (1991)

1991
[18]

In: GICOLAG 2006

Hooker, J.N.: Discrete global optimization with binary decision diagrams. In: GICOLAG 2006. Vienna, Austria (December 2006)

2006
[19]

In: Gomes, C., Sellmann, M

Hooker, J.N.: Decision diagrams and dynamic programming. In: Gomes, C., Sellmann, M. (eds.) CPAIOR 2013 Proceedings. LNCS, vol. 7874, pp. 94–110. Springer (2013)

2013
[20]

In: Beck, J.C

Hooker, J.N.: Job sequencing bounds from decision diagrams. In: Beck, J.C. (ed.) Principles and Practice of Constraint Programming (CP 2017). LNCS, vol. 10416, pp. 565–578. Springer (2017)

2017
[21]

In: J¨ unger, M., Naddef, D

Lemar´ echal, C.: Lagrangian relaxation. In: J¨ unger, M., Naddef, D. (eds.) Computational Combinatorial Optimization. Lecture Notes in Computer Science, vol. 2241, pp. 112–156. Springer (2001)

2001
[22]

Management Science 35, 177–191 (1989)

Ow, P.S., Morton, T.E.: The single machine early/tardy problem. Management Science 35, 177–191 (1989)

1989
[23]

Optimiza- tion Software, New York (1987)

Polyak, B.T.: Introduction to Optimization (translated from Russian). Optimiza- tion Software, New York (1987)

1987
[24]

Mathematical Programming (to appear)

Serra, T., Hooker, J.N.: Compact representation of near-optimal integer programming solutions. Mathematical Programming (to appear)

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [25]

International Journal of Production Research 55, 1707–1719 (2017)

Ying, K.C., Lin, S.W., Lu, C.C.: Eﬀective dynamic dispatching rule and constructive heuristic for solving single-machine scheduling problems with a common due window. International Journal of Production Research 55, 1707–1719 (2017)

work page 2017

[2] [8]

Computers and Operations Research 28, 787–801 (2001)

Biskup, D., Feldman, M.: Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates. Computers and Operations Research 28, 787–801 (2001)

work page 2001

[3] [1]

In: Bessi` ere, C

Andersen, H.R., Hadˇ zi´ c, T., Hooker, J.N., Tiedemann, P.: A constraint store based on multivalued decision diagrams. In: Bessi` ere, C. (ed.) Principles and Practice of Constraint Programming (CP 2007). LNCS, vol. 4741, pp. 118–132. Springer (2007)

work page 2007

[4] [2]

In: Pesant, G

Bergman, D., Cir´ e, A.A., van Hoeve, W.J.: Improved constraint propagation via Lagrangian decomposition. In: Pesant, G. (ed.) Principles and Practice of Constraint Programming (CP 2015). LNCS, vol. 9255, pp. 30–38. Springer (2015)

work page 2015

[5] [3]

Constraints 20, 346–361 (2015)

Bergman, D., Cir´ e, A.A., van Hoeve, W.J.: Lagrangian bounds from decision diagrams. Constraints 20, 346–361 (2015)

work page 2015

[6] [4]

INFORMS Journal on Computing 26, 253–268 (2013)

Bergman, D., Cir´ e, A.A., van Hoeve, W.J., Hooker, J.N.: Optimization bounds from binary decision diagrams. INFORMS Journal on Computing 26, 253–268 (2013)

work page 2013

[7] [5]

INFORMS Journal on Computing 28, 47–66 (2014)

Bergman, D., Cir´ e, A.A., van Hoeve, W.J., Hooker, J.N.: Discrete optimization with binary decision diagrams. INFORMS Journal on Computing 28, 47–66 (2014)

work page 2014

[8] [6]

Springer (2016)

Bergman, D., Cir´ e, A.A., van Hoeve, W.J., Hooker, J.N.: Decision Diagrams for Optimization. Springer (2016)

work page 2016