Enhanced Filtering Algorithms for the Euclidean Traveling Salesperson Problem and its variants in Constraint Logic Programming

• URL: http://arxiv.org/abs/2608.10881v1
• Date: Tue, 11 Aug 2026 12:58:02 GMT
• Title: Enhanced Filtering Algorithms for the Euclidean Traveling Salesperson Problem and its variants in Constraint Logic Programming
• Abstract summary: The Traveling Salesperson Problem (TSP) is one of the best-known problems in computer science and arises in many engineering applications.<n>We propose new filtering algorithms, implemented in Constraint Logic Programming (CLP), that exploit such geometric information to achieve stronger constraint propagation than existing approaches.
• Score: 46.390064640459
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Traveling Salesperson Problem (TSP) is one of the best-known problems in computer science and arises in many engineering applications, such as smart vehicles and intelligent transportation systems. In the "Euclidean" case, each node is defined by its coordinates in the plane and distances are computed using the Euclidean metric. In the Constraint Programming (CP) literature, the Euclidean TSP is typically addressed by computing the full distance matrix and treating it as a general case; however this approach ignores the geometric information carried by the points' coordinates. In this work, we propose new filtering algorithms, implemented in Constraint Logic Programming (CLP), that exploit such geometric information to achieve stronger constraint propagation than existing approaches. Moreover, we show how this methodology can be extended to other Euclidean variants of the TSP, including the Euclidean Generalized Traveling Salesperson Problem (EGTSP), which is relevant in practical routing and logistics applications. Experimental results demonstrate the computational advantages of the proposed approach.

Related papers

• Boundary condition enforcement with PINNs: a comparative study and verification on 3D geometries [0.0]
  Physics-informed neural networks (PINNs) have been studied extensively as a novel technique for solving forward and inverse problems in physics and engineering.<n>There have been limited studies of PINNs on complex three-dimensional geometries, as the lack of mesh and the reliance on the strong form of the partial differential equation (PDE) make boundary condition enforcement challenging.<n>This work represents a step in the direction of establishing PINNs as a mature numerical method, capable of competing head-to-head with incumbents such as the finite element method.
  arXiv  Detail & Related papers  (2025-12-16T22:15:01Z)
• Fast computation of the TGOSPA metric for multiple target tracking via unbalanced optimal transport [0.0]
  In multiple target tracking, it is important to be able to evaluate the performance of different tracking algorithms.<n>The trajectory generalized optimal sub-pattern assignment metric (TGOSPA) is a recently proposed metric for such evaluations.<n>We present an approximation algorithm for evaluating the TGOSPA metric, based on casting the TGOSPA problem as an unbalanced multimarginal optimal transport problem.
  arXiv  Detail & Related papers  (2025-03-12T14:51:03Z)
• Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization [7.114174944371803]
  The problem of finding suitable point embedding Euclidean distance information point pairs arises both as a core task and as a sub-machine learning learning problem. In this paper, we aim to solve this problem given a minimal number of samples.
  arXiv  Detail & Related papers  (2024-10-22T13:02:12Z)
• A GREAT Architecture for Edge-Based Graph Problems Like TSP [10.48061333321108]
  We propose a novel GNN-based and edge-focused neural model called Graph Edge Attention Network (GREAT)<n>Using GREAT as an encoder to capture the properties of a routing problem instance, we build a reinforcement learning framework.<n>Our framework is among the first to tackle non-Euclidean variants of these problems and competitive results among learning-based benchmarks.
  arXiv  Detail & Related papers  (2024-08-29T17:07:43Z)
• Fuse, Reason and Verify: Geometry Problem Solving with Parsed Clauses from Diagram [78.79651421493058]
  We propose a neural-symbolic model for plane geometry problem solving (PGPS) with three key steps: modal fusion, reasoning process and knowledge verification. For reasoning, we design an explicable solution program to describe the geometric reasoning process, and employ a self-limited decoder to generate solution program autoregressively. We also construct a large-scale geometry problem dataset called PGPS9K, containing fine-grained annotations of textual clauses, solution program and involved knowledge solvers.
  arXiv  Detail & Related papers  (2024-07-10T02:45:22Z)
• OTClean: Data Cleaning for Conditional Independence Violations using Optimal Transport [51.6416022358349]
  sys is a framework that harnesses optimal transport theory for data repair under Conditional Independence (CI) constraints. We develop an iterative algorithm inspired by Sinkhorn's matrix scaling algorithm, which efficiently addresses high-dimensional and large-scale data.
  arXiv  Detail & Related papers  (2024-03-04T18:23:55Z)
• A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean TSP [0.0]
  This paper uses multidimensional scaling to first project the points from a non-Euclidean space into a Euclidean space, enabling the generation of a convex hull that initializes the algorithm. To evaluate the proposed algorithm, non-Euclidean spaces are created by adding separators to the TSPLIB data-set, or by using the L1 norm as a metric.
  arXiv  Detail & Related papers  (2023-02-05T13:56:19Z)
• On a class of geodesically convex optimization problems solved via Euclidean MM methods [50.428784381385164]
  We show how a difference of Euclidean convexization functions can be written as a difference of different types of problems in statistics and machine learning. Ultimately, we helps the broader broader the broader the broader the broader the work.
  arXiv  Detail & Related papers  (2022-06-22T23:57:40Z)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  We propose Deep Policy Dynamic Programming (D PDP) to combine the strengths of learned neurals with those of dynamic programming algorithms. D PDP prioritizes and restricts the DP state space using a policy derived from a deep neural network, which is trained to predict edges from example solutions. We evaluate our framework on the travelling salesman problem (TSP) and the vehicle routing problem (VRP) and show that the neural policy improves the performance of (restricted) DP algorithms.
  arXiv  Detail & Related papers  (2021-02-23T15:33:57Z)
• Constraint Programming Algorithms for Route Planning Exploiting Geometrical Information [91.3755431537592]
  We present an overview of our current research activities concerning the development of new algorithms for route planning problems. The research so far has focused in particular on the Euclidean Traveling Salesperson Problem (Euclidean TSP) The aim is to exploit the results obtained also to other problems of the same category, such as the Euclidean Vehicle Problem (Euclidean VRP), in the future.
  arXiv  Detail & Related papers  (2020-09-22T00:51:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.