Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with hop constraints

We present several node-oriented formulations for a Hop Constrained Minimal Spanning Tree (HMST) problem. These formulations are based on the well known Miller-Tucker-Zemlin [1] subtour elimination constraints. Liftings to these inequalities are ‘borrowed’ from the literature and a new class of liftings for the same constraints is also presented. We show that the proposed liftings are not dominated by the previously known liftings. We present some lower bounding schemes for the HMST which are based on lagrangean relaxation combined with subgradient optimization. We present some computational results taken from a set of complete graphs with up to 40 nodes.