复制标题
DOI：
10.1007/3-540-63938-1_46
复制
发表时间：
1997-09
期刊：
影响因子：
--
通讯作者：
中科院分区：
文献类型：
--
作者：
从多面体的角度研究了多层交叉最小化问题。在介绍了多层交叉最小化问题的整数规划形式之后，我们研究了两层的情况，并推导出了相关多面体的几类面片。对二层和三层实例的初步计算结果表明，如果进行更深入的多面体研究，在分枝切割法中使用相应的面片定义不等式可能只会产生实用的算法。
We study the multi-layer crossing minimization problem from a polyhedral point of view. After the introduction of an integer programming formulation of the multi-layer crossing minimization problem, we examine the 2-layer case and derive several classes of facets of the associated polytope. Preliminary computational results for 2- and 3-layer instances indicate, that the usage of the corresponding facet-defining inequalities in a branch-and-cut approach may only lead to a practically useful algorithm, if deeper polyhedral studies are conducted.