Jonathan,
The following pointers to CP literature (on using relaxations for the
TSP) may be useful for you, if you plan to implement your own cost-based
circuit propagator.
* The assignment problem relaxation (works well for asymmetric TSPs and
for TSP-TW) has been studied in a sequence of papers by Focacci et al.,
e.g.,
Filippo Focacci, Andrea Lodi, Michela Milano: Embedding Relaxations in
Global Constraints for Solving TSP and TSPTW. Ann. Math. Artif. Intell.
34(4): 291-311 (2002)
Filippo Focacci, Andrea Lodi, Michela Milano: A Hybrid Exact Algorithm
for the TSPTW. INFORMS Journal on Computing 14(4): 403-417 (2002)
* Domain filtering based on the Held-Karp 1-tree relaxation has recently
been investigated by Benchimol et al:
Pascal Benchimol et al.: Improving the Held and Karp Approach with
Constraint Programming. CPAIOR 2010: 40-44
Cheers,
--Willem
_______________________________________________
Gecode users mailing list
[email protected]
https://www.gecode.org/mailman/listinfo/gecode-users
