Multi valued decision diagrams for multi machine sequencing problems
Session date: 8 July 2024
Session host: Eghonghon Eigbe
Summary:
Decision diagrams can be used for solving optimization problems. Apart from the more popular approach of using them constructively to build solutions in a top-down manner, they can also serve as a constraint store and be incrementally refined by filtering out infeasible arcs until only feasible solutions remain. Existing work has explored single machine sequencing problems or multi machine sequencing problems with identical or very similar machines. In our current WIP, I am extending this to generalize multi resource scheduling scenarios where resources are not necessarily identical, operations can be assigned to one or more resources, etc.. This requires the development of new state representations, merging rules, dominance rules, and more closely related to CP, refinement rules for removing infeasible edges. In this session, I will provide explanations of what has been done so far in the hopes of triggering a discussion that validates and/or challenges our current ideas. An honorable mention will also be made of a small success story with incorporating reinforcement learning for one of the steps in decision diagram based branch and bound.
Relevant papers
-
Multi-machine scheduling lower bounds using decision diagrams
Pim van den Bogaerdt, and Mathijs de Weerdt
Operations Research Letters, Jul 2018
We consider parallel multi-machine scheduling with due times, where a partition of jobs is given where jobs in the same partition have a common release time, possibly precedence constraints, and cannot overlap. A formulation of decision diagrams for this problem greatly improves upon a more natural extension of the state-of-the-art for single-machine scheduling, and can provide decent lower bounds, outperforming existing solvers given the same short runtime limit, for problem instances with large time scales and tight due times.
-
A Constraint Store Based on Multivalued Decision Diagrams
H. R. Andersen, T. Hadzic, J. N. Hooker, and 1 more author
In Principles and Practice of Constraint Programming – CP 2007, Jul 2007
The typical constraint store transmits a limited amount of information because it consists only of variable domains. We propose a richer constraint store in the form of a limited-width multivalued decision diagram (MDD). It reduces to a traditional domain store when the maximum width is one but allows greater pruning of the search tree for larger widths. MDD propagation algorithms can be developed to exploit the structure of particular constraints, much as is done for domain filtering algorithms. We propose specialized propagation algorithms for alldiff and inequality constraints. Preliminary experiments show that MDD propagation solves multiple alldiff problems an order of magnitude more rapidly than traditional domain propagation. It also significantly reduces the search tree for inequality problems, but additional research is needed to reduce the computation time.
-
Lower Bounds for Uniform Machine Scheduling Using Decision Diagrams
Pim Bogaerdt, and Mathijs Weerdt
In Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Jul 2019
We propose a relaxed decision diagram (DD) formulation for obtaining lower bounds on uniform machine scheduling instances, based on separators to separate jobs on different machines. Experiments on the total tardiness for instances with tight due times show that for obtaining nontrivial bounds, it is important to partition the DD nodes on a layer based on their machine finishing time. When the number of jobs is small, DDs provide stronger bounds in less time than a time-indexed LP relaxation.
-
Multivalued Decision Diagrams for Sequencing Problems
Andre A. Cire, and Willem-Jan Hoeve
Operations Research, Jul 2013
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.