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. ... Read more

For causal inference, sufficient overlap is needed. It is possible to use propensity scores with the positivity assumption to ensure overlap is present. However, positivity is not enough to properly identify the region of overlap. For this, propensity scores need to be used in combination with density estimation. This project aims to evaluate this method, discovering in which scenarios it performs well or fails in identifying the region of overlap. More specifically, how it scales with more features or outliers, and how using different classifiers affects the performance. The method was tested with samples from a simulated dataset. The predicted overlap was compared with the true overlap of the known distributions.
Following the experiments, the method seems to perform best when the treatment and control groups share one region of overlap. In this case, logistic regression works best out of the classifiers that were tested. The overall performance drops when the two groups have multiple regions of overlap. For this, the random forest classifier performs best instead. Throughout all scenarios, the performance of the model drops with increasing dimensionality. Furthermore, having a small percentage of outliers only slightly affects the model. With more outliers, logistic regression is the only classifier further affected. ... Read more