  The hop-constrained Steiner tree problem (HSTP) is a generalization of the
classical Steiner tree problem. It asks for a minimum cost subtree that spans
some specified nodes of a given graph, such that the number of edges between
each node of the tree and its root respects a given hop limit. This NP-hard
problem has many variants, often modeled as integer linear programs. Two of the
models are so-called assignment and partial-ordering based models, which yield
(up to our knowledge) the best two state-of-the-art formulations for the
variant Steiner tree problem with revenues, budgets, and hop constraints
(STPRBH). The solution of the HSTP and its variants such as the STPRBH and the
hop-constrained minimum spanning tree problem (HMSTP) is a hop-constrained
tree, a rooted tree whose depth is bounded by a given hop limit. This paper
provides some theoretical results that show the polyhedral advantages of the
partial-ordering model over the assignment model for this class of problems.
Computational results in this paper and the literature for the HSTP, STPRBH,
and HMSTP show that the partial-ordering model outperforms the assignment model
in practice, too; it has better linear programming relaxation and solves more
instances.
