Conventional bounding methods for spanning tree problems often struggle to incorporate additional complex constraints. In this project we use approaches that are very efficient in dealing with complex constraints in path-based problems, and adjust them to fit tree-based structures.