Decision diagrams have steadily become more prominent in the field of combinatorial optimization, being able to outperform the state-of-the-art in e.g. scheduling problems[13]. They have proven even more capable with the introduction of methods such as decision diagram-based Branch & Bound. Often, layer-based binary decision diagram (BDD) encodings are used to encode the problem domain, where a layered structure determines the decisions and decision variables. Recently, state-based multivalued decision diagram (MDD) encodings have also been considered. These do not rely on a layered structure, as instead, each state makes its decisions on the variables independently of other states. This allows for more flexible decision-making as states do not have to compromise with other states on the decisions they make.

This thesis compares these newer state-based MDDs with the commonly used layer-based BDDs, while also introducing and evaluating heuristics for the state-based MDDs. These heuristics include a new beam restriction heuristic that limits the branching factor of the MDDs, a dynamic variable ordering strategy adapted for the new state-based context, and a new local bound for the maximum independent set problem (MISP).

The experiments of this thesis show that the state-based MDDs generally outperform the layer-based BDDs in both runtime and search tree size. Only for some instances with low graph densities, the state-based MDDs were slower. This is resolved with the newly introduced beam restrictions, which can significantly lower the runtime. This speedup is also shown for the graph coloring problem, although the application of the beam restrictions is not as straightforward there as with the MISP. Both the dynamic variable ordering and the new local bound for the MISP show great promise in increasing the efficiency of the search, but are both held back by the additional overhead they introduce. Fortunately, these two techniques can share the added overhead while gaining the combined benefits, resulting in great performance for the MISP when both methods are used together.