|
|
--- |
|
|
language: en |
|
|
tags: |
|
|
- graph-neural-networks |
|
|
- combinatorial-optimization |
|
|
- tsp |
|
|
- floydnet |
|
|
- diffusion-models |
|
|
- pytorch |
|
|
license: mit |
|
|
datasets: |
|
|
- ocxlabs/FloydNet_TSP_demo |
|
|
--- |
|
|
|
|
|
# FloydNet (Non-Metric TSP / Explicit TSP) |
|
|
|
|
|
## Model Summary |
|
|
|
|
|
**FloydNet** is a graph reasoning architecture designed to mimic the execution of algorithms via a learned, global Dynamic Programming operator. This checkpoint (`_exp`) is trained to solve the **Non-Metric (Explicit) Traveling Salesman Problem**, where edge weights are generic integers and do not necessarily obey the triangle inequality. |
|
|
|
|
|
Unlike standard GNNs that rely on local message passing, FloydNet maintains and refines a global all-pairs relationship tensor, achieving 3-WL (2-FWL) expressive power. |
|
|
|
|
|
## Model Details |
|
|
|
|
|
* **Model ID:** `ocxlabs/FloydNet_TSP_exp` |
|
|
* **Architecture:** FloydNet (Deep relational layers with Pivotal Attention) |
|
|
* **Task:** General Traveling Salesman Problem (Non-Metric) |
|
|
* **Paper:** [FloydNet: A Learning Paradigm for Global Relational Reasoning](https://arxiv.org/abs/2601.19094) |
|
|
* **Demo Dataset:** [ocxlabs/FloydNet_TSP_demo](https://huggingface.co/datasets/ocxlabs/FloydNet_TSP_demo) |
|
|
|
|
|
## Performance |
|
|
|
|
|
On General TSP instances (N=100-200), FloydNet demonstrates capabilities significantly exceeding strong heuristics: |
|
|
* **Optimality:** Achieves an optimality rate of **99.8%** (with 10 samples) on held-out graphs, compared to **38.8%** by the Linkern heuristic. |
|
|
* **Exact Solutions:** On single-solution instances, it finds the exact optimal tour in **92.6%** of cases. |
|
|
|
|
|
## Usage: Inference & Evaluation |
|
|
|
|
|
Reproducing TSP results at full scale is computationally heavy. For convenience, we provide a small demo dataset and pre-trained checkpoints. |
|
|
|
|
|
### 1. Preparation |
|
|
Download the demo dataset from [Hugging Face](https://huggingface.co/datasets/ocxlabs/FloydNet_TSP_demo). Unzip it and place the extracted folder under `example/data/`. |
|
|
|
|
|
### 2. Inference |
|
|
Run inference in `--test_mode` using `torchrun`. The command below assumes a single-node setup with 8 GPUs. Ensure `--subset` is set to `exp`. |
|
|
|
|
|
```bash |
|
|
source .venv/bin/activate |
|
|
cd example |
|
|
|
|
|
torchrun \ |
|
|
--nproc_per_node=8 \ |
|
|
-m TSP.run \ |
|
|
--subset exp \ |
|
|
--output_dir ./outputs/TSP_exp \ |
|
|
--load_checkpoint path/to/TSP_exp/epoch_01000.pt \ |
|
|
--test_mode \ |
|
|
--split_factor 1 \ |
|
|
--sample_count_per_case 10 |
