NGSaddle

A framework for discovering adversarial, hard benchmark instances for any computational problem (e.g., TSP, SAT, and FSSP) using gradient-free black-box optimization (Nevergrad).

Disclaimer: NGSaddle is licensed under Apache-2.0. Solver backends and optional dependencies—including Concorde and IBM CP Optimizer—are governed by their own licences and are not distributed as part of NGSaddle.

Features

Used (present and actively used)

• Pluggable instance encodings per domain
• Pluggable solver as the hardness objective (Concorde, CP-SAT / CP-Optimizer)
• Noise-robust repeat protocol (per-call seeds + median)
• Configurable hardness aggregation
• Configurable objective function shaping (steer the optimizer)
• Parallel execution — two-level multiprocessing for batch / HPC sweeps
• Per-eval logging (zarr)
• Post-processing — sort + champion extraction
• Plot generation — optimizer trajectories (best / confidence band / per-run)

Experimental (present, not actively used)

• External instance seeding
• Steady-state / sliding-window evaluation mode
• Re-solving / re-timing logged instances

Installation

You can install NGSaddle via pip:

pip install ngsaddle

Solver Dependencies

To evaluate instances, NGSaddle relies on the external solver you want to test. You must install and configure the specific solver backend required for your domain (e.g., Concorde, CP Optimizer, or any custom solver you are evaluating).

Usage and Pipeline

The core NGSaddle library accepts configuration parameters as standard Python dictionaries. The optimization pipeline consists of three main stages:

1. gen (Generation): Spawns a parallel pool of Nevergrad optimizers to search the instance space. Evaluation results and checkpoints are logged using chunked Zarr arrays to a logs/ directory.
2. transform: Post-processes the logs, sorts the instances by hardness, and extracts the "champions" (the hardest instances found).
3. plot: Generates trajectory plots showing the optimizer's progress (e.g., best running time found over time, confidence bands).

Example Scripts

While the core library is pure Python, this repository includes several example domains (TSP, SAT, Ham, JSSP) that wrap the library.

For instance, in the TSP/ directory, there is an exp.py wrapper script that parses a user-provided JSON configuration file and converts it into the Python dictionary required by NGSaddle:

cd TSP
python exp.py --file example.json

Advanced HPC Usage

NGSaddle is designed for robust parallel execution on large machines:

• Core Affinity: It uses psutil to limit process CPU affinity, avoiding OS thread oversubscription.
• Preemption Safety: Intermediate results are saved frequently. If a cluster job is preempted or you hit Ctrl+C, the progress is safely preserved in the .zarr datasets and can be resumed. You can also press s in the terminal to trigger a manual save.