# Improved Job sequencing Bounds from Decision Diagrams

arXiv: https://arxiv.org/abs/1908.07076 · HTML: https://mlsanity.com/paper/1908.07076/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Aug 2019.

## Built on by (most cited first, 2 of 2)

- [FastDOG: Fast Discrete Optimization on GPU](https://mlsanity.com/paper/2111.10270/) (2021)
- [Improving the filtering of Branch-And-Bound MDD solver (extended)](https://mlsanity.com/paper/2104.11951/) (2021)

## Abstract (arXiv)

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