Multivalued Decision Diagrams for Sequencing Problems

• 成果类型: Article
• 署名作者: Cire, Andre A.; van Hoeve, Willem-Jan
• 署名单位: Carnegie Mellon University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2013.1221
• 发表日期: 2013
• 页码: 1411-1428
• 关键词: traveling salesman problem; algorithms; branch

摘要

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.