HW5 — TSP with Neighborhoods (TSPN) Benchmark Pack (TSPLIB → Circles)

This repository provides a fixed, reproducible benchmark for HW5 so that everyone runs on the same input data and results are directly comparable.

In HW5, we do not visit fixed nodes. Instead, each “city” is a region (circle/polygon). A city is considered visited if the tour visits any (x,y) point inside that region.

This pack uses TSPLIB kroA100 and converts sampled nodes into circle regions.

---

What’s Inside

• instances/inst_00.json ... inst_29.json
  30 benchmark instances. Each instance contains 50 circle regions (cities) and the exact radius used.
• tools/grade.py
  Autograder skeleton that validates point-in-region and recomputes tour length.
• tools/visualize_folium.py
  Minimal folium visualization helper (circles + chosen points + tour polyline).
• data/tsplib/kroA100.tsp (optional, instructor use)
  Only needed if you want to regenerate instances.

---

Problem Definition (TSP with Neighborhoods)

Given N=50 circular regions ( R_i ), each with center ( c_i=(x_i,y_i) ) and radius ( r ):

1. Choose one point per region: ( p_i=(\hat{x}_i,\hat{y}_i) )
2. Ensure each chosen point is inside its region: [ |p_i - c_i| \le r ]
3. Choose a visit order (a Hamiltonian cycle over region IDs).
4. The tour length is computed using the chosen points in the given order: [ \sum_{k=0}^{N-1} |p_{order[k]} - p_{order[(k+1)\bmod N]}| ] Goal: minimize the tour length.

---

Frozen Instance Generation Spec

• Base TSPLIB: kroA100
• Instances: 30
• Regions per instance: N = 50
• Seeds: 1000 ... 1029
• Neighborhood type: circles
• Radius rule (per instance):
  • Sample 50 nodes from kroA100 using the instance seed.
  • Compute each center’s nearest-neighbor distance; let ( d_{nn} ) be the mean.
  • Set a common radius for all circles: [ r = \alpha \cdot d_{nn} ]
• Alpha: α = 0.20

Each instances/inst_XX.json contains the computed numeric radius.

---

Input Contract (Instance JSON)

Path: instances/inst_XX.json

Key fields:

• regions: list of 50 regions, each:
  • id (0..49)
  • cx, cy center coordinates
  • r radius

Example:

{
  "name": "inst_07",
  "n": 50,
  "alpha": 0.2,
  "radius": 12.34,
  "regions": [
    {"id": 0, "cx": 123.0, "cy": 456.0, "r": 12.34}
  ]
}