Multivalued Decision Diagrams for Sequencing Problems

Andre A. Cire () and Willem-Jan van Hoeve ()
Additional contact information
Andre A. Cire: Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Willem-Jan van Hoeve: Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213

Operations Research, 2013, vol. 61, issue 6, 1411-1428

Abstract: Sequencing problems are among the most prominent problems studied in operations research, with primary application in, e.g., scheduling and routing. We propose a novel approach to solving generic sequencing problems using multivalued decision diagrams (MDDs). Because an MDD representation may grow exponentially large, we apply MDDs of limited size as a discrete relaxation to the problem. We show that MDDs can be used to represent a wide range of sequencing problems with various side constraints and objective functions, and we demonstrate how MDDs can be added to existing constraint-based scheduling systems. Our computational results indicate that the additional inference obtained by our MDDs can speed up a state-of-the art solver by several orders of magnitude, for a range of different problem classes.

Keywords: sequencing; single machine scheduling; networks/graphs; constraint programming; decision diagrams (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2013.1221 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:61:y:2013:i:6:p:1411-1428

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().