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

The paper presents several node-oriented formulations for a Hop Constrained Minimal Spanning Tree (HMST) problem. These formulations are based on the well knwon Miller-Tucker-Zemlin 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. The paper shows that the proposed liftings are not dominated by the previously known liftings. It presents some lower bounding schemes for the HMST which are based on lagrangean relaxation combined with subgradient optimization. The paper presents some computational results taken from a set of complete graphs with up to 40 nodes.