Talks and Poster Presentations (with Proceedings-Entry):
J. Maschler, G. Raidl:
"Multivalued Decision Diagrams for a Prize-Collecting Sequencing Problem";
- 2018-08-31; in: "PATAT 2018: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling}",
Johannes Maschler · GĻunther R. Raidl
Abstract Recent years have shown that multivalued decision diagrams (MDD) are a powerful tool for approaching combinatorial optimization prob-lems (COPs). Relatively compact relaxed and restricted MDDs are employed to obtain dual bounds and heuristic solutions and provide opportunities for new branching schemes. We consider a prize-collecting sequencing problem in which a subset of given jobs has to be found that is schedulable and yields max-imum total prize. The primary aim of this work is to study diﬀerent methods for creating relaxed MDDs for this problem. To this end, we adopt and extend the two main MDD compilation approaches found in the literature: top down construction and incremental reﬁnement. In a series of computational experi-ments these methods are compared. The results indicate that for our problem the incremental reﬁnement method produces MDDs with stronger bounds. Moreover, heuristic solutions are derived by compiling restricted MDDs and by applying a general variable neighborhood search (GVNS). Here we observe that the top down construction of restricted MDDs is able to yield better solutions as the GVNS on small to medium-sized instances.
Keywords Sequencing · multivalued decision diagrams · incremental reﬁnement · particle therapy patient scheduling
Electronic version of the publication:
Created from the Publication Database of the Vienna University of Technology.