Research map / Learning theory and algorithms / Sample complexity
Alternative Filtering for the Weighted Circuit Constraint: Comparing Lower Bounds for the TSP and Solving TSPTW
Sylvain Ducomman, Hadrien Cambazard, Bernard Penz
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use exact reduced costs instead of LP reduced costs for assignment filtering (ablation) | Assignment filtering · TSPLIB ATSP | search nodes: 1175424,4 -> 4852,3 | Improved |
| Held and Karp filtering instead of ln-path | CP TSP model · TSPLIB ATSP | root gap (%): 6,3 -> 1,0 | Improved |
| ln-path instead of Held and Karp | CP TSPTW model · Dumas TSPTW | root gap median (%): 2,00 -> 0,72 | Improved |
| ln-path instead of Held and Karp | CP TSPTW model · Ascheuer TSPTW | root gap mean (%): 0,76 -> 0,50 | Improved |
| ln-path instead of Held and Karp | CP TSPTW model · Pesant TSPTW | root gap mean (%): 4,71 -> 5,06 | Hurt |
| ln-path instead of assignment bound | CP TSP model · TSPLIB ATSP | root gap (%): 15,0 -> 6,3 | Improved |
| ln-path instead of Held and Karp | CP TSP model · TSPLIB ATSP | time (s): 25,7 -> 426,9 | Hurt |
| ln-path instead of Held and Karp | CP TSPTW model · Ohlmann TSPTW (150/200 vertices) | cpu time: 10,02 -> 45,54 | Hurt |
| ln-path instead of Held and Karp | CP TSPTW model · Dumas w80 exact solve | instances solved: 18/20 -> 18/20 | No clear effect |
| ln-path instead of assignment | CP TSPTW model · Dumas w80 exact solve | instances solved: 12/20 -> 18/20 | Improved |
| ln-path instead of Held and Karp | CP TSPTW model · Ascheuer exact solve | instances solved: 29/50 -> 35/50 | Improved |
Closest papers by meaning
- Solving the Asymmetric Traveling Salesman Problem via Trace-Guided Cost Augmentation (NeurIPS 2025 · similarity 0.86)
- Improved Filtering for the Euclidean Traveling Salesperson Problem in CLP(FD) (AAAI 2020 · similarity 0.86)
- Improved Approximation Algorithms for Clustered TSP and Subgroup Planning (AAAI 2025 · similarity 0.82)
- DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem (AAAI 2025 · similarity 0.82)
- A Fast Exact Solver with Theoretical Analysis for the Maximum Edge-Weighted Clique Problem (AAAI 2024 · similarity 0.82)
- Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times (NeurIPS 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
