期刊
NETWORKS
卷 80, 期 2, 页码 178-192出版社
WILEY
DOI: 10.1002/net.22086
关键词
hop constraint; hop-indexed model; integer programming; linear programming relaxation; network design; Steiner tree
资金
- FCT -Fundacao para a Ciencia e a Tecnologia [UIDB/04561/2020]
This article explores the relation between the linear programming relaxation of two classes of models for the Steiner tree problem with hop constraints, and finds that the linear programming relaxation of node-based models is implied by the linear programming relaxation of arc-based models.
We study the relation between the linear programming relaxation of two classes of models for the Steiner tree problem with hop constraints. One class is characterized by having hop-indexed arc variables. Although such models have proved to have a very strong linear programming bound, they are not easy to use because of the huge number of variables. This has motivated some studies with models involving fewer variables that use, instead of the hop-indexed arc variables, hop-indexed node variables. In this article, we contextualize the linear programming relaxation of these node-based models in terms of the linear programming relaxation of known arc-based models. We show that the linear programming relaxation of a general node-based model is implied by the linear programming relaxation of a straightforward arc-based model.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据