[gecode-users] Lower bound for Branch-and-bound

[Willem-Jan van Hoeve]

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