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.
A more accurate relaxation is the Minimum Spanning Arborescence (MSA) relaxation, since it does not relax the orientation of the graph. This relaxation has been studied by @cite_29 @cite_28 who provide a @math time filtering algorithm based on primal dual linear programs. The best algorithm for computing a MSA has been provided by @cite_4 . Their algorithm runs in @math worst case time, but it does not provide reduced costs that are used for pruning. Thus, it could be used to create a constraint with a @math time consistency checking but the complete filtering algorithm remains in @math time. The Lagrangian MSA relaxation, with a MSA computation based on Edmonds' algorithm, has been suggested in @cite_17 . This method was very accurate but unfortunately unstable. Also, @cite_3 report that the MSA based Held and Karp scheme lead to disappointing results.
@cite_4 @cite_28 @cite_29 @cite_3 @cite_17
1867111234 1542480886 2013561074 1517248951 109225361
The paper introduces the MST(G,T,W) constraint, which is specified on two graph variables G and T and a vector W of scalar variables. The constraint is satisfied if T is a minimum spanning tree of G, where the edge weights are specified by the entries of W. We develop algorithms that filter the domains of all variables to bound consistency. Constraint Programming (CP) has been successfully applied to several combinatorial optimization problems. One of its advantages is the availability of complex global constraints performing efficient propagation and interacting with each other through shared variables. However, CP techniques have shown their limitations in dealing with optimization problems since the link between the objective function and problem decision variables is often quite loose and does not produce an effective propagation. We propose to integrate optimization components in global constraints, aimed at optimally solving a relaxation corresponding to the constraint itself. The optimal solution of the relaxation provides pieces of information which can be exploited in order to perform pruning on the basis of cost-based reasoning. In fact, we exploit reduction rules based on lower bound and reduced costs calculation to remove those branches which cannot improve the best solution found so far. The interest of integrating efficient well-known Operations Research (OR) algorithms into CP is mainly due to the smooth interaction between CP domain reduction and information provided by the relaxation acting on variable domains which can be seen as a i>communication channel among different techniques. We have applied this technique to symmetric and asymmetric Traveling Salesman Problem (TSP) instances both because the TSP is an interesting problem arising in many real-life applications, and because pure CP techniques lead to disappointing results for this problem. We have tested the proposed optimization constraints using ILOG solver. Computational results on benchmarks available from literature, and comparison with related approaches are described in the paper. The proposed method on pure TSPs improves the performances of CP solvers, but is still far from the OR state of the art techniques for solving the problem. However, due to the flexibility of the CP framework, we could easily use the same technique on TSP with Time Windows, a time constrained variant of the TSP. For this type of problem, we achieve results that are comparable with state of the art OR results. In this paper, new lower bounds for the asymmetric travelling salesman problem are presented, based on spanning arborescences. The new bounds are combined in an additive procedure whose theoretical performance is compared with that of the Balas and Christofides procedure (1981). Both procedures have been imbedded in a simple branch and bound algorithm and experimentally evaluated on hard test problems. So far, edge-finding is the only one major filtering algorithm for unary resource constraint with time complexity O(nlog n). This paper proposes O(nlog n) versions of another two filtering algorithms: not-first not-last and propagation of detectable precedences. These two algorithms can be used together with the edge-finding to further improve the filtering. This paper also propose new O(nlog n) implementation of fail detection (overload checking).