Network-Optimization-Problems

This project implements a Polynomial-Time Approximation Scheme (PTAS)–style algorithm for the Traveling Salesman Problem with Neighborhoods (TSPN), restricted to the case where all neighborhoods are vertical integer segments on an integer grid.

The implementation follows the high-level structure of the PTAS given in:

TSP With Locational Uncertainty: The Adversarial Model
(PTAS for TSP with neighborhoods via quadtree dissection + portals)

…but adapted and simplified into a fully working and practical prototype:

• ✔️ No preprocessing
• ✔️ Integer-aligned quadtree decomposition
• ✔️ Portals on boundaries
• ✔️ Exact leaf solver
• ✔️ Portal-based stitching
• ✔️ Outputs an approximate TSP tour

---

✨ Features

1. Vertical Integer Segments

Each neighborhood is given as a tuple:

(x, y1, y2)

2. Integer-Aligned Quadtree

Squares use power-of-two side lengths and integer boundaries.

3. Portals

m portals per side uniformly placed.

4. Exact Leaf Solver

Each leaf:

• enumerates candidate integer points
• samples if needed
• brute-forces one-point-per-segment choices
• computes:
  • best closed tour
  • all portal-to-portal paths

5. Portal-Based Stitching

Internal squares merge child solutions and build parent DP states.

6. Global Tour Extraction

Root returns the None closed tour stored in sol_cache.

---

⚙️ Usage Example

segments = [
    (0, 0, 1),
    (10, 40, 41),
    (40, 0, 1),
    (50, 40, 41),
]

tour, L = ptas_tspn_quadtree(segments, m=4, max_leaf_segments=4, min_size=1)
print("Approx Tour Length:", L)
print(tour)

---

📂 Structure

PTAS_TSPN/
├── Segment, Portal
├── Square
├── quadtree construction
├── solve_leaf_exact()
├── stitch_children()
├── solve_square()
└── ptas_tspn_quadtree()

---

🎯 Approximation Behavior

✔️ Better accuracy when max_leaf_segments is increased,

but only for small or moderate global segment counts.

✔️ For large instances:

• computational cost grows exponentially inside leaves
• PTAS theory requires constant-size leaves
• cannot arbitrarily increase max_leaf_segments

Practical rule:

4–10 segments per leaf balances accuracy and runtime.

---

⚠️ Limitations

• Not a full rigorous PTAS (stitching is heuristic)
• Leaf solver exponential in leaf size
• Handles vertical integer segments only

---

📘 Reference

PTAS section of “TSP With Locational Uncertainty: The Adversarial Model”
(Adversarial neighborhoods, dissection trees, portals)