Recent works on cost based relaxations have improved Constraint Programming (CP) models for the Traveling Salesman Problem (TSP). We provide a short survey over solving asymmetric TSP with CP. Then, we suggest new implied propagators based on general graph properties. We experimentally show that such implied propagators bring robustness to pathological instances and highlight the fact that graph structure can significantly improve search heuristics behavior. Finally, we show that our approach outperforms current state of the art results.
However, other implied constraints provide additional filtering that may help the resolution process. For instance, Quesada @cite_12 suggested the general propagator which maintains the transitive closure and the dominance tree of the graph variable. However, its running time, @math in the worst case, makes it unlikely to be profitable in practice. A faster constraint, also based on the concept of dominance, is the constraint. It is nothing else but a simplification of the constraint @cite_26 recently improved to a @math worst case time complexity @cite_18 . Given a graph variable @math and a node @math , such a constraint ensures that @math is an arborescence rooted in node @math . More precisely, it enforces GAC over the conjunction of the following properties: @math has no circuit, each node is reachable from @math and, each node but @math has exactly one predecessor. Such a filtering can also be used to define the by switching @math with @math and predecessors with successors.
@cite_18 @cite_26 @cite_12
2156899428 2247768113
This paper revisits the tree constraint introduced in [2] which partitions the nodes of a n-nodes, m-arcs directed graph into a set of node-disjoint anti-arborescences for which only certain nodes can be tree roots. We introduce a new filtering algorithm that enforces generalized arc-consistency in O(n + m) time while the original filtering algorithm reaches O(nm) time. This result allows to tackle larger scale problems involving graph partitioning. Constrained path problems have to do with finding paths in graphs subject to constraints. We present a constraint programming approach for solving the Ordered disjoint-paths problem (ODP), i.e., the Disjoint-paths problem where the pairs are associated with ordering constraints. In our approach, we reduce ODP to the Ordered simple path with mandatory nodes problem (OSPMN), i.e., the problem of finding a simple path containing a set of mandatory nodes in a given order. The reduction of the problem is motivated by the fact that we have an appropriate way of dealing with OSPMN based on DomReachability, a propagator that implements a generalized reachability constraint on a directed graph based on the concept of graph variables. The DomReachability constraint has three arguments: (1) a flow graph, i.e., a directed graph with a source node; (2) the dominance relation graph on nodes and edges of the flow graph; and (3) the transitive closure of the flow graph. Our experimental evaluation of DomReachability shows that it provides strong pruning, obtaining solutions with very little search. Furthermore, we show that DomReachability is also useful for defining a good labeling strategy. These experimental results give evidence that DomReachability is a useful primitive for solving constrained path problems over directed graphs.