Using Hop-Indexed Models For Constrained Spanning and Steiner Tree Models
Using Hop-Indexed Models For Constrained Spanning and Steiner Tree Models
复制标题
使用跳索引模型进行约束生成和斯坦纳树模型
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
L. Gouveia
中科院分区：
文献类型：
--
作者：
L. Gouveia
网络设计问题的几个模型只涉及一组二元变量，一个且只有一个变量X ij对应于底层图的每个弧（i，j）。这些公式的缺点是，它们通常需要指数数量的约束来强制连接。减少这种约束的数量可以通过使用额外的一组变量来实现，这些变量可以被认为是多余的，因为它们对于导出问题的有效公式是不必要的。然而，附加到新变量的附加信息可能会大大减少为同一问题导出有效模型所需的约束条件的数量。
Several models for network design problems involve only one set of binary variables, with one and only one variable X ij corresponding to each arc (i, j) of the underlying graph. The disadvantage of these formulations is that they usually need an exponential number of constraints to enforce connectivity. Reducing the number of such constraints can be achieved by using an additional set of variables which may be considered superfluous in the sense that they are not necessary for deriving a valid formulation for the problem. However, the additional information attached to the new variables may reduce considerably the number of constraints needed to derive a valid model for the same problem.