The salesman and the tree: the importance of search in CP

DOI10.1007/S10601-014-9178-2MaRDI QIDQ272000zbMATH OpenOpenAlexFDO

Authors Jean-Guillaume Fages, Xavier Lorca, Louis-Martin Rousseau

Publication date 20 April 2016

Published in Constraints (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10601-014-9178-2

zbMATH Keywords

constraint programmingglobal constraintssearchtraveling salesman problemoperational research

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• Constrained spanning trees and the traveling salesman problem
• Comparison of algorithms for the degree constrained minimum spanning tree
• Solving TSP through the integration of OR and CP techniques
• Solving diameter-constrained minimum spanning tree problems by constraint programming
• Constraint Programming for the Diameter Constrained Minimum Spanning Tree Problem

Cites work

• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• CP(Graph): Introducing a Graph Computation Domain in Constraint Programming
• Embedding relaxations in global constraints for solving TSP and TSPTW
• Explaining circuit propagation
• Improved filtering for weighted circuit constraints
• Lower and upper bounds for the degree-constrained minimum spanning tree problem
• Optimization-oriented global constraints
• Reasoning from last conflict(s) in constraint programming
• Simpler and Incremental Consistency Checking and Arc Consistency Filtering Algorithms for the Weighted Spanning Tree Constraint
• The Weighted Spanning Tree Constraint Revisited
• The traveling-salesman problem and minimum spanning trees: Part II
• Using Lagrangian dual information to generate degree constrained spanning trees

Cited in

(3)

• NeuroPrim: an attention-based model for solving NP-hard spanning tree problems
• scientific article; zbMATH DE number 7455732 (Why is no real title available?)
• Improving the robustness of EPS to solve the TSP

Describes a project that uses

Uses Software

• Concorde
• LKH
• TSPTW

This page was built for publication: The salesman and the tree: the importance of search in CP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q272000)