[Back]

J. Maschler, G. Raidl:
"Multivalued Decision Diagrams for a Prize-Collecting Sequencing Problem";
Talk: Patat2018, Wien; 2018-08-28 - 2018-08-31; in: "PATAT 2018: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling}", (2018), 375 - 397.

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 different 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 refinement. In a series of computational experi-ments these methods are compared. The results indicate that for our problem the incremental refinement 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 refinement · particle therapy patient scheduling

https://publik.tuwien.ac.at/files/publik_273918.pdf