Looking for edge-equitable spanning trees

This paper studies the Ordered Spanning Tree Problem, where the weights of the edges of the tree are sorted and then linearly combined using a previously given coefficients vector. Depending on the coefficients, several objectives can be incorporated to the problem. We pay special attention to the search of spanning trees with balanced weights, i.e., where the differences among the weights are, in some sense, minimized. To solve the problem, we propose two Integer Programming formulations, one based on flow and the other one on the Miller–Tucker–Zemlin constraints. We analyze several potential improvements for both the formulations whose behaviors are checked by means of a computational experiment. Finally, we show how both the formulations can be adapted to incorporate to the objective non‐linear functions of the weights.