Multivalued Decision Diagrams for Sequencing Problems

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

Full description

Saved in:
Bibliographic Details
Published in:Operations research 2013-11, Vol.61 (6), p.1411-1428
Main Authors: Cire, Andre A., van Hoeve, Willem-Jan
Format: Article
Language:English
Subjects:
Analysis
Boolean
constraint programming
Decision analysis
decision diagrams
Employment
Graph theory
Integer programming
METHODS
Multiple criteria decision making
networks/graphs
Operations research
Optimization
Routing
Scheduling
Scheduling (Management)
sequencing
Sequential scheduling
single machine scheduling
Studies
Traveling salesman problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0030-364X
1526-5463
DOI:10.1287/opre.2013.1221