  Several novel mixed-integer linear and bilinear formulations are proposed for
the optimum communication spanning tree problem. They implement the
distance-based approach: graph distances are directly modeled by continuous,
integral, or binary variables, and interconnection between distance variables
is established using the recursive Bellman-type conditions or using matrix
equations from algebraic graph theory. These non-linear relations are used
either directly giving rise to the bilinear formulations, or, through the big-M
reformulation, resulting in the linear programs. A branch-and-bound framework
of Gurobi 9.0 optimization software is employed to compare performance of the
novel formulations on the example of an optimum requirement spanning tree
problem with additional vertex degree constraints. Several real-world
requirements matrices from transportation industry are used to generate a
number of examples of different size, and computational experiments show the
superiority of the two novel linear distance-based formulations over the the
traditional multicommodity flow model.
