Metric UFL Approximation Project

This repository contains the final code, experiment pipeline, and paper for an empirical study of classical approximation algorithms for the metric uncapacitated facility location (UFL) problem.

The implemented methods are:

• greedy star heuristic
• local search with add/delete/1-swap
• primal-dual heuristic inspired by Jain--Vazirani
• deterministic LP rounding
• randomized LP rounding
• optional 2-swap local-search follow-up

The project scope is strictly uncapacitated facility location. OR-Library cap files are loaded only as uncapacitated surrogate stress tests because the current model ignores capacities and demands by design.

Canonical directories

The repository has a small active workflow and a larger set of saved artifacts. These are the directories that matter for the final project:

• src/ufl: core package
• scripts: CLI runners and report builders
• slurm/final_hpc: ordered final HPC pipeline
• slurm/two_swap_hpc: 2-swap follow-up pipeline
• configs/hpc: per-instance HPC plans
• paper: final writeup
• results/final_hpc: canonical final experiment outputs
• results/two_swap_hpc: canonical 2-swap outputs

Other results/* folders are earlier exploratory runs kept only for reference.

Minimal local workflow

Use the repository root as the working directory and expose the package with PYTHONPATH=src.

Run the smoke suite:

PYTHONPATH=src python scripts/run_experiments.py --suite smoke

Run the default synthetic suite:

PYTHONPATH=src python scripts/run_experiments.py \
  --suite default \
  --output results/default

Run a single saved benchmark file:

PYTHONPATH=src python scripts/run_experiments.py \
  --suite benchmark \
  --benchmark-path data/benchmarks/example.json

Run the full Euclidean benchmark suite:

PYTHONPATH=src python scripts/run_experiments.py \
  --suite uflib_euclidean \
  --output results/uflib_euclidean

HPC workflow

The final cluster campaign is submitted in order with:

bash scripts/submit_final_hpc.sh

This pipeline writes:

• Slurm logs to logs/slurm/final_hpc/
• ordered results to results/final_hpc/

The 2-swap follow-up uses:

bash scripts/submit_2swap_hpc.sh

and writes to:

• logs/slurm/two_swap_hpc/
• results/two_swap_hpc/

Benchmarks

Download the public benchmark archives with:

python scripts/fetch_benchmarks.py --set uflib_euclidean uflib_kmedian orlib_cap

The archives and extracted directories are stored under data/benchmarks/.

Report generation

Build the report-ready summary tables and figure bundle from the final HPC results with:

python scripts/build_final_report.py

This writes artifacts under results/final_hpc/report/.

The paper source is in paper/main.tex. See paper/README.md for LaTeX notes.

Validation

Recommended lightweight checks:

PYTHONPATH=src pytest -q
python -m py_compile src/ufl/*.py src/ufl/algorithms/*.py src/ufl/solvers/*.py scripts/*.py
bash -n slurm/final_hpc/*.slurm
bash -n slurm/two_swap_hpc/*.slurm

Project layout

src/ufl/                  core models, algorithms, I/O, experiment driver
scripts/run_experiments.py local CLI entrypoint
scripts/run_benchmark_plan.py per-instance HPC runner
scripts/merge_results.py  merge k-median array outputs
scripts/build_final_report.py final summary tables and figure builder
scripts/submit_final_hpc.sh ordered final Slurm submission
scripts/submit_2swap_hpc.sh ordered 2-swap Slurm submission
paper/                    writeup and figure bundle
tests/                    smoke and regression checks

Notes

• Gurobi is optional for import and test collection, but exact IP and LP-based methods require it at runtime.
• The active local-search implementation supports 1-swap and 2-swap. Larger swap sizes are intentionally not implemented.
• The final paper uses the results/final_hpc/ and results/two_swap_hpc/ outputs, not every historical run under results/.