For a directed graph, a Minimum Weight Arborescence (MWA) rooted at a vertex r is a directed spanning tree rooted at r with the minimum total weight. We define the MinArborescence constraint to solve constrained arborescence problems (CAP) in Constraint Programming (CP). A filtering based on the LP reduced costs requires O(|V|~2) where |V| is the number of vertices. We propose a procedure to strengthen the quality of the LP reduced costs in some cases, also running in O(|V|~2). Computational results on a variant of CAP show that the additional filtering provided by the constraint reduces the size of the search tree substantially.
展开▼
机译：对于指向图，根为顶点R根的最小重量植物（MWA）是以最小总重量的r根的定向生成树。我们定义了Minarborepery约束，以解决约束编程（CP）中的约束的树突问题（CAP）。基于LP降低成本的滤波需要O（| v |〜2），其中V |是顶点的数量。我们提出了一种过程在某些情况下加强LP的质量降低成本，也在O（| v |〜2）中运行。帽变体上的计算结果表明，由约束提供的附加滤波基本上减少了搜索树的大小。
展开▼
