⚛️ quantum physics

Cutting-plane methodology via quantum optimization for solving the Traveling Salesman Problem

This paper proposes an iterative framework combining dynamic subtour elimination, arc preprocessing, and both classical and quantum (including D-Wave annealing and hybrid) optimization methods to significantly reduce model size and improve computational performance for solving the Traveling Salesman Problem.

Original authors: Alessia Ciacco, Luigi Di Puglia Pugliese, Francesca Guerriero

Published 2026-04-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alessia Ciacco, Luigi Di Puglia Pugliese, Francesca Guerriero

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a traveling salesperson with a map of 30 cities. Your goal is simple: visit every city exactly once and return home, but you want to do it in the shortest possible distance to save money on gas.

This is the Traveling Salesman Problem (TSP). While it sounds easy, it is a notorious mathematical nightmare. If you have 10 cities, there are millions of possible routes. If you have 30, the number of routes is so huge it exceeds the number of atoms in the universe. Trying to check every single route is impossible.

This paper is about a new way to solve this puzzle using Quantum Computers, but with a clever trick to make the quantum computer's job easier.

Here is the breakdown of their strategy, using simple analogies:

1. The Big Problem: The "Subtour" Trap

When you ask a computer to find the shortest route, it often gets lazy. Instead of finding one big loop that visits all cities, it might find a few small loops.

The Analogy: Imagine you tell a robot to visit every house on a street and come back. Instead of walking the whole street, the robot might just walk in a circle around three houses, then stop, then walk in a circle around three other houses. It visited everyone, but it didn't make one continuous trip.
The Math: In computer terms, these are called "subtours." To stop the computer from doing this, mathematicians have to add rules (constraints) saying, "You cannot make a small circle; you must keep going."
The Nightmare: The problem is that for 30 cities, the number of rules needed to stop every possible small circle is astronomical. It's like trying to write a rulebook for every possible way a child could mess up a game. The book becomes too thick to read, and the computer crashes.

2. The Solution: Two Smart Tricks

The authors realized that trying to write all the rules at once is impossible. So, they used two strategies to shrink the problem down to a size a quantum computer can handle.

Trick A: The "Cutting-Plane" Method (The Detective)

Instead of writing all the rules at the start, they start with a very simple set of rules. They let the computer guess a route.

How it works:
1. The computer guesses a route.
2. The "Detective" checks the route. "Hey, you made a small circle around these three cities! That's not allowed."
3. The Detective adds one specific rule just to stop that specific mistake.
4. The computer tries again.
5. Repeat until the computer finds a perfect, single loop.
The Benefit: Instead of carrying a library of rules, the computer only carries the few rules it actually needs to fix its mistakes. This is called the Cutting-Plane Approach (CPA).

Trick B: "Arc Filtering" (The Map Shrinker)

Before the computer even starts guessing, the authors use a pre-check to remove bad roads.

The Analogy: Imagine you are driving from New York to Los Angeles. You know you will never take a detour to a city in the opposite direction or a tiny, winding dirt road that adds 100 miles. You only care about the main highways.
How it works: They look at the map and delete any road that is clearly too long or inefficient. If a road is the 10th best option to get from City A to City B, they might delete it, assuming the best 5 options are enough.
The Benefit: This shrinks the map significantly. Fewer roads mean fewer choices for the computer, making the puzzle much smaller.

3. The Quantum Part: The Magic Machine

Once they shrunk the problem using the two tricks above, they fed it into a Quantum Computer (specifically a D-Wave machine).

What is a Quantum Computer? Think of a classical computer as a person trying to find the exit of a maze by walking one path at a time. A quantum computer is like a ghost that can walk down all paths at the same time, feeling for the one that feels the "lightest" (shortest).
The Challenge: Quantum computers are currently small and fragile. They can't handle the huge, messy problems we usually throw at them.
The Result: Because the authors used their "Detective" (CPA) and "Map Shrinker" (CAF) tricks, they were able to feed a problem size (30 cities) into the quantum computer that it had never solved before.

4. The Results: Classical vs. Quantum

The authors tested three ways to solve the problem:

The Old Way (Classical): Trying to solve the whole thing with a standard computer.
- Result: It worked for small maps, but for 30 cities, the computer got stuck in the "rulebook" problem and couldn't finish.
The Direct Quantum Way: Sending the problem straight to the quantum computer without the "Detective" trick.
- Result: The quantum computer got confused by the sheer number of rules and failed to find a good route.
The Hybrid Way (The Winner): Using the "Detective" and "Map Shrinker" tricks, then letting a Hybrid Solver do the work.
- What is a Hybrid Solver? Imagine a team where a human (classical computer) does the heavy lifting and planning, but calls in a psychic (quantum computer) to check the most promising paths quickly.
- Result: This team solved the 30-city problem perfectly! They found the best route in about 2 minutes, whereas the old way couldn't even start.

Summary

The paper is essentially saying: "Quantum computers are powerful, but they are currently too small to handle big, messy problems. However, if we use smart classical tricks to clean up the problem first (removing bad roads and only adding rules when necessary), we can get quantum computers to solve real-world puzzles that were previously impossible."

They didn't just build a better engine; they built a better map so the engine could actually drive.

1. Problem Definition

The paper addresses the Traveling Salesman Problem (TSP), a classic NP-hard combinatorial optimization problem where the goal is to find the minimum-cost Hamiltonian cycle visiting a set of cities exactly once.

Core Challenge: The primary bottleneck in TSP formulations, particularly for Integer Linear Programming (ILP) and Quantum Annealing (QA), is the exponential growth of subtour elimination constraints (SECs). To ensure a single valid tour, constraints must prevent the formation of disconnected cycles (subtours). Explicitly including all $O(2^n)$ SECs renders the model computationally intractable for even moderately sized instances ( $n > 20$ ) on both classical and quantum hardware.
Quantum Limitations: Current quantum hardware (e.g., D-Wave QPUs) has limited qubit counts and connectivity. Encoding complex constraints like SECs directly into Quadratic Unconstrained Binary Optimization (QUBO) models via penalty terms results in massive problem sizes and high energy landscape ruggedness, often preventing the discovery of feasible solutions.

2. Methodology

The authors propose a hybrid framework that integrates classical operations research techniques with quantum optimization. The methodology consists of two main reduction strategies applied to both classical and quantum solvers:

A. Cost-based Arc Filtering (CAF) Preprocessing

Mechanism: A preprocessing step that reduces the solution space by eliminating "non-promising" arcs.
Process: For each node, outgoing arcs are sorted by cost, and only the $k$ nearest neighbors are retained.
Goal: Reduce the number of decision variables (arcs) and the density of the optimization model while preserving the existence of a Hamiltonian cycle.

B. Iterative Cutting-Plane Approach (CPA)

Mechanism: A "lazy constraint generation" technique. Instead of including all SECs a priori, the model is solved initially with only degree constraints (ensuring each city is visited once).
Process:
1. Solve the relaxed model.
2. Detect if the solution contains subtours (disconnected cycles).
3. If subtours exist, generate and add the specific SECs required to break them.
4. Re-solve the model.
5. Repeat until a single Hamiltonian cycle is found.
Goal: Drastically reduce the number of constraints in the active model, keeping it manageable for solvers.

C. Optimization Paradigms Tested

The study evaluates the proposed framework across three distinct paradigms:

Classical Exact (CILP): Solves the full ILP with all SECs (baseline) vs. CPA.
Direct Quantum (QPU): Formulates the problem as a QUBO (penalizing constraints in the objective function) and executes directly on the D-Wave Advantage2 QPU.
Hybrid Quantum-Classical: Uses the Constrained Quadratic Model (CQM) where constraints are explicit. This is solved using D-Wave's LeapCQMHybrid solver, which orchestrates classical metaheuristics (e.g., tabu search) and quantum annealing cycles asynchronously.

3. Key Contributions

First Application of Lazy Constraints in QA: This work represents the first application of an iterative lazy constraint generation approach (CPA) within a Quantum Annealing framework for TSP.
Bridging the Scalability Gap: By combining CAF (variable reduction) and CPA (constraint reduction), the authors successfully solve TSP instances up to 30 nodes using quantum/hybrid methods, a significant leap from previous literature which was limited to $\le 15$ nodes.
Comparative Analysis of Modeling Formalisms: The paper provides a rigorous comparison between QUBO (penalty-based, direct QPU) and CQM (constraint-based, hybrid solver), demonstrating that explicit constraint handling via hybrid solvers is superior for complex combinatorial problems.
Empirical Validation: Extensive computational experiments on TSPLIB benchmarks (specifically berlin52 subsets) validate the efficacy of the proposed strategies.

4. Computational Results

Classical Optimization

Performance: The CPA + CAF combination solved instances up to $n=45$ in fractions of a second.
Comparison: The standard CILP (full constraints) failed to construct models for $n \ge 25$ within time limits. CPA reduced the number of constraints by >95% for medium instances and nearly 100% for larger ones compared to CILP.

Direct Quantum (QPU)

QUBO Limitations: Direct execution of the full model (CILP) failed for $n \ge 6$ due to intractable QUBO sizes.
CPA Improvement: Using CPA on the QPU allowed feasible solutions up to $n=10$ (40% feasibility rate).
Scalability Limit: For $n \ge 11$ , the direct QPU approach failed to find feasible solutions, highlighting the hardware constraints of current QPUs regarding problem density and embedding overhead.

Hybrid Quantum-Classical (CQM)

Superior Performance: The hybrid approach using CPA and CAF achieved optimal solutions (0% gap) for all instances up to $n=25$ .
Large Instances: For $n=30$ , the method achieved a 1% optimality gap (6206.03 vs. optimal 6146.65) with a total runtime of ~140 seconds.
Robustness: The hybrid solver maintained high consistency (zero standard deviation in results for $n \le 25$ ), proving that combining classical search with quantum refinement effectively mitigates the complexity of the TSP.

5. Significance and Conclusion

Practical Quantum Advantage: The study demonstrates that while "pure" quantum approaches (direct QPU execution) struggle with the combinatorial explosion of TSP constraints, hybrid quantum-classical approaches combined with advanced preprocessing and lazy constraint generation can solve practically relevant problem sizes.
Methodological Shift: The paper argues that the future of quantum optimization for logistics lies not in forcing complex constraints into penalty-based QUBOs, but in utilizing hybrid solvers that can handle explicit constraints (CQM) while leveraging quantum annealing for local search refinement.
Future Outlook: The authors suggest that as quantum hardware evolves (more qubits, better connectivity), these hybrid frameworks will become even more powerful, potentially narrowing the gap with state-of-the-art classical solvers for larger industrial instances.

In summary, this paper provides a robust blueprint for solving NP-hard routing problems on current quantum hardware by decoupling the problem complexity through iterative constraint generation and graph reduction, rather than attempting to encode the entire problem complexity into the quantum processor at once.